TY - GEN
T1 - A fast algorithm for optimal alignment between similar ordered trees
AU - Jansson, Jesper Andreas
AU - Lingas, Andrzej
PY - 2001/1/1
Y1 - 2001/1/1
N2 - We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. An optimal alignment between S and T which uses at most d blank symbols can be constructed in O(n log n. (maxdeg)4. d2) time, where n = maxf{|S|,|T|} and maxdeg is the maximum degree of a node in S or T. In particular, if the input trees are of bounded degree, the running time is O(n log n. d2).
AB - We present a fast algorithm for optimal alignment between two similar ordered trees with node labels. Let S and T be two such trees with |S| and |T| nodes, respectively. An optimal alignment between S and T which uses at most d blank symbols can be constructed in O(n log n. (maxdeg)4. d2) time, where n = maxf{|S|,|T|} and maxdeg is the maximum degree of a node in S or T. In particular, if the input trees are of bounded degree, the running time is O(n log n. d2).
UR - http://www.scopus.com/inward/record.url?scp=84957024825&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 3540422714
SN - 9783540422716
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 232
EP - 240
BT - Combinatorial Pattern Matching - 12th Annual Symposium, CPM 2001, Proceedings
PB - Springer Verlag
T2 - 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001
Y2 - 1 July 2001 through 4 July 2001
ER -