Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Reticulation-Visible Networks
Bordewich, Magnus; Semple, Charles
Authors
Charles Semple
Abstract
Let X be a finite set, N be a reticulation-visible network on X , and T be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not N displays T. Furthermore, for all |X|≥1, we show that N has at most 8|X|−7 vertices in total and at most 3|X|−3 reticulation vertices, and that these upper bounds are sharp.
Citation
Bordewich, M., & Semple, C. (2016). Reticulation-Visible Networks. Advances in Applied Mathematics, 78, 114-141. https://doi.org/10.1016/j.aam.2016.04.004
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 13, 2016 |
Online Publication Date | Apr 27, 2016 |
Publication Date | Jul 1, 2016 |
Deposit Date | Apr 20, 2016 |
Publicly Available Date | Mar 29, 2024 |
Journal | Advances in Applied Mathematics. |
Print ISSN | 0196-8858 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 78 |
Pages | 114-141 |
DOI | https://doi.org/10.1016/j.aam.2016.04.004 |
Files
Accepted Journal Article
(743 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
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