Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
A universal tree-based network with the minimum number of reticulations
Bordewich, Magnus; Semple, Charles
Authors
Charles Semple
Abstract
A tree-based network N on X is universal if every rooted binary phylogenetic X-tree is a base tree for N. Hayamizu and, independently, Zhang constructively showed that, for all positive integers n, there exists an universal tree-based network on n leaves. For all n, Hayamizu’s construction contains Θ(n!) reticulations, while Zhang’s construction contains Θ(n2) reticulations. A simple counting argument shows that a universal tree-based network has Ω(nlogn) reticulations. With this in mind, Hayamizu as well as Steel posed the problem of determining whether or not such networks exist with O(nlogn) reticulations. In this paper, we show that, for all n, there exists a universal tree-based network on n leaves with O(nlogn) reticulations.
Journal Article Type | Article |
---|---|
Acceptance Date | May 6, 2018 |
Online Publication Date | May 30, 2018 |
Publication Date | Dec 11, 2018 |
Deposit Date | May 10, 2018 |
Publicly Available Date | May 30, 2019 |
Journal | Discrete Applied Mathematics |
Print ISSN | 0166-218X |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 250 |
Pages | 357-362 |
DOI | https://doi.org/10.1016/j.dam.2018.05.010 |
Public URL | https://durham-repository.worktribe.com/output/1327131 |
Files
Accepted Journal Article
(253 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2018 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)
Presentation / Conference Contribution
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Presentation / Conference Contribution
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Presentation / Conference Contribution
On the approximation complexity hierarchy.
(2011)
Presentation / Conference Contribution
Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.
(2010)
Presentation / Conference Contribution
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