ALIGNMENT OF TREES - AN ALTERNATIVE TO TREE EDIT

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(\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 algorithm for tree edit when deg(T-1) and deg(T-2) are smaller than the depths of T-1 and T-2. 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.