Magnús M. HalldórssonGiven two rooted, labeled, unordered trees, the common subtree problem is to find a bijective matching between subsets of vertices of the trees of maximum cardinality which preserves labels and ancestry relationship. The tree editing distance problem is to determine the least cost sequence of additions, deletions and changes that converts a tree into another given tree. Both problems are known to be hard to approximate within some constant factor in general. We present polynomial algorithms for several special classes of trees as well as a tighter approximation hardness proof, which together comes close to characterizing the complexity of both problems on all interesting special classes of trees. We also present the first approximation algorithm with non-trivial approximation ratios. In particular, we achieve a ratio of log^2 n, where n is the number of vertices in the trees.
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.Keisuke Tanaka
School of Information Science, Japan Advanced Institute of Science and Technology -- Hokuriku
Tatsunokuchi, Ishikawa 923-12, Japan
tanaka@jaist.ac.jp