Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
On the computational complexity of the rooted subtree prune and regraft distance
Bordewich, M.; Semple, C.
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
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search