Journal
THEORETICAL COMPUTER SCIENCE
Volume 233, Issue 1-2, Pages 33-50Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(97)00278-8
Keywords
approximation algorithms; common subtree; common point set; computational biology
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available