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|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||September 2008|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|