New results on optimizing rooted triplets consistency
From MaRDI portal
Publication:708349
DOI10.1016/j.dam.2010.03.004zbMath1221.05041MaRDI QIDQ708349
Jaroslaw Byrka, Sylvain Guillemot, Jesper Jansson
Publication date: 11 October 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://infoscience.epfl.ch/record/140352/files/51c.pdf
approximation algorithm; phylogenetic tree; hardness of approximation; supertree; pseudorandomness; rooted triplet
Related Items
Optimizing phylogenetic supertrees using answer set programming, Unnamed Item, Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract), Building a small and informative phylogenetic supertree, Kernel and fast algorithm for dense triplet inconsistency, Comparing and aggregating partially resolved trees, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees, The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets, On the weighted quartet consensus problem, The matroid structure of representative triple sets and triple-closure computation, Orthology relations, symbolic ultrametrics, and cographs, Constructing the R* consensus tree of two trees in subcubic time, Trinets encode tree-child and level-2 phylogenetic networks, Binets: fundamental building blocks for phylogenetic networks, Encoding and constructing 1-nested phylogenetic networks with trinets, Complexity insights of the minimum duplication problem, Gene tree correction for reconciliation and species tree inference: complexity and algorithms, Complexity of modification problems for best match graphs, Complexity Insights of the Minimum Duplication Problem, The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rooted maximum agreement supertrees
- Inferring a level-1 phylogenetic network from a dense set of rooted triplets
- Analytic solutions for three taxon ML trees with variable rates across sites
- The complexity of reconstructing trees from qualitative characters and subtrees
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- On the complexity of constructing evolutionary trees
- A supertree method for rooted trees
- Constructing the maximum consensus tree from rooted Triples
- Reconstruction of rooted trees from subtrees
- Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
- Maximum agreement and compatible supertrees
- Hardness of fully dense problems
- A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
- Algorithmic construction of sets for k -restrictions
- Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
- Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time
- Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Determining the Evolutionary Tree Using Experiments
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
- Ranking Tournaments
