A 3-approximation algorithm for the subtree distance between phylogenies
Type of content
Journal Article
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury. Mathematics and Statistics.
Journal Title
Journal ISSN
Volume Title
Language
Date
2008
Authors
Bordewich, M.
McCartin, C.
Semple, C.
Abstract
In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known.
Description
Citation
Bordewich, M., McCartin, C., Semple, C. (2008) A 3-approximation algorithm for the subtree distance between phylogenies. Journal of Discrete Algorithms, 6(3), pp. 458-471.