Reticulation-visible networks

2015/08/21 by Bordewich, Magnus, Semple, Charles · 2 citations
#05C85 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1508.05424

Abstract

Let X be a finite set, \mathcal N be a reticulation-visible network on X, and \mathcal T be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not \mathcal N displays \mathcal T. Furthermore, for all |X|≥ 1, we show that \mathcal 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.

Cited by

• Exploiting Low Scanwidth to Resolve Soft Polytomies
• When Many Trees Go to War

Related

• Bounding the Size of a Network Defined By Visibility Property
• Locating a Phylogenetic Tree in a Reticulation-Visible Network in Quadratic Time
• Counting Phylogenetic Networks with Few Reticulation Vertices: Galled and Reticulation-Visible Networks
• Solving Tree Containment Problem for Reticulation-visible Networks with Optimal Running Time
• Locating a Tree in a Reticulation-Visible Network in Cubic Time