Bordewich, M. and Semple, C. (2005) 'On the computational complexity of the rooted subtree prune and regraft distance.', Annals of combinatorics., 8 (4). pp. 409-423.
Abstract
The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is xed parameter tractable when parameterised by the distance between the two trees.
| Item Type: | Article |
|---|---|
| Keywords: | Rooted phylogenetic tree, Rooted subtree prune, Regraft. |
| Full text: | (AM) Accepted Manuscript Download PDF (188Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/s00026-004-0229-z |
| Publisher statement: | The original publication is available at www.springerlink.com |
| Date accepted: | No date available |
| Date deposited: | 13 October 2008 |
| Date of first online publication: | January 2005 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
