Name
Title | ||
|---|---|---|
Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. |
Abstract | ||
|---|---|---|
A phylogenetic network is a rooted acyclic digraph whose leaves are labeled with a set of taxa. The tree containment problem is a fundamental problem arising from model validation in the study of phylogenetic networks. It asks to determine whether or not a given network displays a given phylogenetic tree over the same leaf set. It is known to be NP-complete in general. Whether or not it remains NP-complete for stable networks is an open problem. We make progress towards answering that question by presenting a quadratic time algorithm to solve the tree containment problem for a new class of networks that we call genetically stable networks, which include tree-child networks and comprise a subclass of stable networks. |
Year | Venue | Field |
|---|---|---|
2015 | IWOCA | Discrete mathematics,Combinatorics,Phylogenetic tree,Open problem,Subclass,Binary tree,Time complexity,Taxon,Digraph,Mathematics,Phylogenetic network |
DocType | Citations | PageRank |
Conference | 4 | 0.48 |
References | Authors | |
3 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Philippe Gambette | 1 | 77 | 9.61 |
| Andreas D. M. Gunawan | 2 | 33 | 6.84 |
| Anthony Labarre | 3 | 69 | 9.62 |
| Stéphane Vialette | 4 | 648 | 48.10 |
| Louxin Zhang | 5 | 890 | 96.47 |