Bordewich, M.McCartin, C.Semple, C.2008-11-092008-11-092008Bordewich, 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.http://hdl.handle.net/10092/1774In 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.enJournal ArticleFields of Research::230000 Mathematical Sciences::239900 Other Mathematical Sciences::239901 Biological Mathematicshttps://doi.org/10.1016/j.jda.2007.10.002