On the approximation of largest common subtrees and largest common point sets
On the approximation of largest common subtrees and largest common point sets
复制标题
DOI：
10.1016/s0304-3975(97)00278-8
复制
发表时间：
2000-02-28
影响因子：
1.1
通讯作者：
Halldórsson, MM
中科院分区：
文献类型：
--
作者：
Akutsu, T;Halldórsson, MM
本文研究了分子生物学中最大公共子树和最大公共点集的可逼近性问题。证明了对于任何n> 0，除非NP子集等于或等于ZPP，否则这两个问题不能在多项式时间内以n（1-n）的因子逼近，而给出了一个在O（n/logn）的因子内逼近这两个问题的一般搜索算法.对于有界度的树，提出了一种改进的算法，该算法在O（n/ log（2）n）的因子内逼近最大公共子树。此外，最大公共子树问题的几个变种进行了研究。(C)2000 Elsevier Science B. V.保留所有权利。
This paper considers the approximability of the largest common subtree and the largest common point-set problems, which have applications in molecular biology. It is shown that the problems cannot be approximated within a factor of n(1-epsilon) in polynomial time for any epsilon > 0 Unless NP subset of or equal to ZPP, while a general search algorithm which approximates both problems within a factor of O(n/log n) is presented. For trees of bounded degree, an improved algorithm which approximates the largest common subtree within a factor of O(n/ log(2) n) is presented. Moreover, several variants of the largest common subtree problem are studied. (C) 2000 Elsevier Science B.V. All rights reserved.