Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
| dc.creator | To, Thu-Hien | |
| dc.creator | Habib, Michel | |
| dc.date | 2009-01-12 | |
| dc.date.accessioned | 2026-07-07T12:28:27Z | |
| dc.date.available | 2026-07-07T12:28:27Z | |
| dc.description | Given a dense triplet set $\mathcal{T}$, there arise two interesting questions: Does there exists any phylogenetic network consistent with $\mathcal{T}$? And if so, can we find an effective algorithm to construct one? For cases of networks of levels $k=0$ or 1 or 2, these questions were answered with effective polynomial algorithms. For higher levels $k$, partial answers were recently obtained with an $O(|\mathcal{T}|^{k+1})$ time algorithm for simple networks. In this paper we give a complete answer to the general case. The main idea is to use a special property of SN-sets in a level-k network. As a consequence, we can also find the level-k network with the minimum number of reticulations in polynomial time. | |
| dc.identifier | https://arxiv.org/abs/0901.1657 | |
| dc.identifier | http://arxiv.org/abs/0901.1657 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/215548 | |
| dc.subject | Populations and Evolution | |
| dc.title | Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time | |
| dc.type | text |