Skip to main content

Research Repository

Advanced Search

Reticulation-Visible Networks

Bordewich, Magnus; Semple, Charles

Reticulation-Visible Networks Thumbnail


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 Apr 27, 2017
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
Public URL https://durham-repository.worktribe.com/output/1384045

Files






You might also like



Downloadable Citations