Article ID Journal Published Year Pages File Type
4624519 Advances in Applied Mathematics 2016 28 Pages PDF
Abstract

Let X   be a finite set, NN be a reticulation-visible network on X  , and TT be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not NN displays TT. Furthermore, for all |X|≥1|X|≥1, we show that NN has at most 8|X|−78|X|−7 vertices in total and at most 3|X|−33|X|−3 reticulation vertices, and that these upper bounds are sharp.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,