Approximation and Special Cases of Common Subtrees and Editing Distance
Approximation and Special Cases of Common Subtrees and Editing Distance
复制标题
公共子树和编辑距离的近似和特例
DOI：
10.1007/bfb0009483
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Keisuke Tanaka
中科院分区：
文献类型：
--
作者：
M. Halldórsson;Keisuke Tanaka
给定两棵有根的、有标号的、无序的树，通常的子树问题是在最大基数树的顶点子集之间寻找一个双射匹配，该匹配保持标号和祖先关系。树编辑距离问题是确定将一棵树转换成另一棵树的最小成本的添加、删除和更改序列。这两个问题是众所周知的，很难近似在一些常数的因素在general.We提出多项式算法的几个特殊类的树木，以及更严格的近似硬度证明，这两个问题的复杂性，所有有趣的特殊类的树木。我们还提出了非平凡的近似比的第一近似算法。特别地，我们实现了log2n的比率，其中是树中的顶点数。
Given two rooted, labeled, unordered trees, thecommon subtreeproblem is to find a bijective matching between subsets of vertices of the trees of maximum cardinality which preserves labels and ancestry relationship. Thetree editing distanceproblem 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 log2n, wherenis the number of vertices in the trees.