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.
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.
| Item Type: | Article |
|---|---|
| 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
| Export: | |
| Look up in GoogleScholar |
