Reticulation-visible networks

详细信息    查看全文

• 作者：Magnus Bordewich^a ; ^{m.j.r.bordewich@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Charles Semple^b ; ^{charles.semple@canterbury.ac.nz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：05C85 ; 68R10
• 刊名：Advances in Applied Mathematics
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：78
• 期：Complete
• 页码：114-141
• 全文大小：622 K

文摘

Let X   be a finite set, N$\mathcal{N}$ be a reticulation-visible network on X  , and 58c55163f03c6b2d14bd2310a" title="Click to view the MathML source">T$\mathcal{T}$ be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not N$\mathcal{N}$ displays 58c55163f03c6b2d14bd2310a" title="Click to view the MathML source">T$\mathcal{T}$. Furthermore, for all c50267db461273" title="Click to view the MathML source">|X|≥1$|X|\ge 1$, we show that N$\mathcal{N}$ has at most 8|X|−7$8|X|-7$ vertices in total and at most 3|X|−3$3|X|-3$ reticulation vertices, and that these upper bounds are sharp.