Skip to main content

Research Repository

Advanced Search

On the computational complexity of the rooted subtree prune and regraft distance

Bordewich, M.; Semple, C.

On the computational complexity of the rooted subtree prune and regraft distance Thumbnail


Authors

C. Semple



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.

Citation

Bordewich, M., & Semple, C. (2005). On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combinatorics, 8(4), 409-423. https://doi.org/10.1007/s00026-004-0229-z

Journal Article Type Article
Publication Date 2005-01
Deposit Date Oct 13, 2008
Publicly Available Date Oct 13, 2008
Journal Annals of Combinatorics
Print ISSN 0218-0006
Electronic ISSN 0219-3094
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 8
Issue 4
Pages 409-423
DOI https://doi.org/10.1007/s00026-004-0229-z
Keywords Rooted phylogenetic tree, Rooted subtree prune, Regraft.
Publisher URL http://www.springerlink.com/openurl.asp?genre=article&eissn=0219-3094&volume=8&issue=4&spage=409

Files

Accepted Journal Article (192 Kb)
PDF

Copyright Statement
The original publication is available at www.springerlink.com







You might also like



Downloadable Citations