Reticulation-Visible Networks

Bordewich, Magnus; Semple, Charles

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