ALIGNMENT OF TREES - AN ALTERNATIVE TO TREE EDIT

In this paper, we propose the alignment of trees as a measure of the s imilarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time c omplexity of this algorithm is O(\T-1\.\T-2\.(deg(T-1) + deg(T-2))(2)) , where \T-i\ is the number of nodes in T-i and deg(T-i) is the degree of T-i, i = 1, 2. The algorithm is faster than the best known algorit hm for tree edit when deg(T-1) and deg(T-2) are smaller than the depth s of T-1 and T-2. For unordered trees, we show that the alignment prob lem can be solved in polynomial time if the trees have a bounded degre e and becomes MAX SNP-hard if one of the trees is allowed to have an a rbitrary 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.