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 -