Bordewich, M. and McCartin, C. and Semple, C. (2008) 'A 3-approximation algorithm for the subtree distance between phylogenies.', Journal of discrete algorithms., 6 (3). pp. 458-471.
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.
|Keywords:||Rooted subtree prune and regraft, Agreement forest.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1016/j.jda.2007.10.002|
|Record Created:||21 Dec 2009 15:20|
|Last Modified:||19 Aug 2010 14:32|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|