Abstract | ||
---|---|---|
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods.We present the first algorithm for (rooted) \textsc{Tree Containment} using the treewidth $t$ of the input network $N$ as parameter, showing that the problem can be solved in $2^{O(t^2)}\cdot|N|$ time and space. |
Year | DOI | Venue |
---|---|---|
2022 | 10.4230/LIPICS.ESA.2022.69 | European Symposium on Algorithms (ESA) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Leo van Iersel | 1 | 0 | 0.68 |
Mark Jones | 2 | 25 | 7.09 |
Mathias Weller | 3 | 1 | 2.39 |