Bordewich, Magnus and Semple, Charles (2018) 'A universal tree-based network with the minimum number of reticulations.', Discrete applied mathematics., 250 . pp. 357-362.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (248Kb)
|Publisher Web site:||https://doi.org/10.1016/j.dam.2018.05.010|
|Publisher 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/|
|Date accepted:||06 May 2018|
|Date deposited:||10 May 2018|
|Date of first online publication:||30 May 2018|
|Date first made open access:||30 May 2019|
Save or Share this output
|Look up in GoogleScholar|