Skip to main content

Research Repository

Advanced Search

A universal tree-based network with the minimum number of reticulations

Bordewich, Magnus; Semple, Charles

A universal tree-based network with the minimum number of reticulations Thumbnail


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.

Citation

Bordewich, M., & Semple, C. (2018). A universal tree-based network with the minimum number of reticulations. Discrete Applied Mathematics, 250, 357-362. https://doi.org/10.1016/j.dam.2018.05.010

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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations