A 3-approximation algorithm for the subtree distance between phylogenies

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

doi:10.1016/j.jda.2007.10.002

A 3-approximation algorithm for the subtree distance between phylogenies

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

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

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
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.
Publisher URL	http://www.sciencedirect.com/science/article/B758J-4RHFVH5-1/2/6d4695ca376998bd5098624f1a4250d9