CVSM Bibliography, Entry [ JiWZ1995TCS ]


Jiang, Tao; Wang, Lusheng; Zhang, Kaizhong: Alignment of trees-an alternative to tree edit; Theoretical Computer Science 143:1, p.137-148; 1995
Library Entries: DOI 10.1016/0304-3975(95)80029-9, sciencedirect
Deskriptoren: CVSM, tree:differencing

Abstract: In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unorderedtrees 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 |T1| is the number of nodes in T1 and deg(T1) is the degree of T1, i = 1.2. The algorithm is faster than the best known algorithm for treeedit 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 MAX SNP-hard if one of the trees is allowed to have an arbitrary degree. In contrast, the edit problem for unordered trees is MAX SNP-hard even if both trees have a bounded degree (Zhang and Jiang, 1994). Finally, multiple alignment of trees is discussed.
(A preliminary version of this paper appeared in the Proc. of CPM'94. Springer. Lecture Notes in Computer Science, Vol. 807, 1994. Submission of this paper in final form to Theoret. Comput. Sci. was invited in view of the strong endorsement contained in the conference reviews.)