Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
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.
Bordewich, M., McCartin, C., & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of discrete algorithms, 6(3), 458-471. https://doi.org/10.1016/j.jda.2007.10.002
Journal Article Type | Article |
---|---|
Publication Date | Sep 1, 2008 |
Deposit Date | Dec 21, 2009 |
Journal | Journal of Discrete Algorithms |
Print ISSN | 1570-8667 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 6 |
Issue | 3 |
Pages | 458-471 |
DOI | https://doi.org/10.1016/j.jda.2007.10.002 |
Keywords | Rooted subtree prune and regraft, Agreement forest. |
Publisher URL | http://www.sciencedirect.com/science/article/B758J-4RHFVH5-1/2/6d4695ca376998bd5098624f1a4250d9 |
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
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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