Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624519 | Advances in Applied Mathematics | 2016 | 28 Pages |
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
Magnus Bordewich, Charles Semple,