Name
Abstract | ||
|---|---|---|
A chief problem in phylogenetics and database theory is the computation of a maximum consistent tree from a set of rooted or un- rooted trees. A standard input are triplets, rooted binary trees on three leaves, or quartets, unrooted binary trees on four leaves. We give exact algorithms constructing rooted and unrooted maximum consistent su- pertrees in time O(2nn5m2 logm) for a set of m triplets (quartets), each one distinctly leaf-labeled by some subset of n labels. The algorithms extend to weighted triplets (quartets). We further present fast exact al- gorithms for constructing rooted and unrooted maximum consistent trees in polynomial space. Finally, for a setT of m rooted or unrooted trees with maximum degree D and distinctly leaf-labeled by some subset of a set L of n labels, we compute, in O(2mDnmm5n6 logm) time, a tree distinctly leaf-labeled by a maximum-size subset X L that all trees in T , when restricted to X, are consistent with. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | binary tree,maximum degree,discrete mathematics,data structure |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Split,Binary tree,Link/cut tree,PSPACE,Degree (graph theory),Database theory,Mathematics,Computation | Journal | abs/0901.3 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leo van Iersel | 1 | 215 | 24.58 |
| Matthias Mnich | 2 | 253 | 25.44 |