期刊
THEORETICAL COMPUTER SCIENCE
卷 233, 期 1-2, 页码 33-50出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(97)00278-8
关键词
approximation algorithms; common subtree; common point set; computational biology
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据