The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets

DOI10.1007/978-3-319-19929-0_23zbMath1432.68577OpenAlexW2296608184MaRDI QIDQ2942263

Jesper Jansson, Eva-Marta Lundell, Andrzej Lingas

Publication date: 20 August 2015

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19929-0_23

zbMATH Keywords

bioinformaticsapproximation algorithmsphylogenetic treerooted tripletsmooth integer program

Mathematics Subject Classification ID

Problems related to evolution (92D15) Approximation algorithms (68W25)

Cites Work

• New results on optimizing rooted triplets consistency
• 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
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• On the complexity of constructing evolutionary trees
• Constructing the maximum consensus tree from rooted Triples
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions