Alignment of trees — an alternative to tree edit

AbstractIn 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 |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 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 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