@inproceedings{c3cfb825c17240ed8316ae34f00ecdbe,
title = "Alignment of Trees: An Alternative to Tree Edit",
abstract = "In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time complexity of this algorithm is O (|T1| · |T2| · (deg(T1) + deg(T2))2), where |Ti | is the number of nodes in Ti and deg(Ti) is the degree of Ti, i = 1, 2. The algorithm is faster than the best known algorithm for tree edit when deg(T1) and deg(T2) are smaller than the depths of T1 and T2. For unordered trees, we show that the alignment problem can be solved in polynomial time if the trees have a bounded degree and becomes NP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is NP-hard even if both trees have a bounded degree [17]. Finally, multiple alignment of trees is discussed.",
keywords = "Lower Segment, Optimal Alignment, Edit Operation, Label Tree, Arbitrary Degree",
author = "Tao Jiang and Lusheng Wang and Kaizhong Zhang",
year = "1994",
month = jun,
doi = "10.1007/3-540-58094-8_7",
language = "English",
isbn = "978-3-540-58094-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "75--86",
editor = "Maxime Crochemore and Gusfield, {Dan }",
booktitle = "Combinatorial Pattern Matching",
address = "Germany",
note = "5th Annual Symposium on Combinatorial Pattern Matching (CPM 1994) ; Conference date: 05-06-1994 Through 08-06-1994",
}