Skip to main content

Research Repository

Advanced Search

A 3-approximation algorithm for the subtree distance between phylogenies

Bordewich, M.; McCartin, C.; Semple, C.

Authors

C. McCartin

C. Semple



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.

Citation

Bordewich, M., McCartin, C., & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of discrete algorithms, 6(3), 458-471. https://doi.org/10.1016/j.jda.2007.10.002

Journal Article Type Article
Publication Date Sep 1, 2008
Deposit Date Dec 21, 2009
Journal Journal of Discrete Algorithms
Print ISSN 1570-8667
Electronic ISSN 1570-8675
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 6
Issue 3
Pages 458-471
DOI https://doi.org/10.1016/j.jda.2007.10.002
Keywords Rooted subtree prune and regraft, Agreement forest.
Public URL https://durham-repository.worktribe.com/output/1522652
Publisher URL http://www.sciencedirect.com/science/article/B758J-4RHFVH5-1/2/6d4695ca376998bd5098624f1a4250d9