The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets

DOI10.1016/j.dam.2018.08.028zbMath1406.05099OpenAlexW2899269379WikidataQ128977062 ScholiaQ128977062MaRDI QIDQ1730227

Andrzej Lingas, Jesper Jansson, Katharina Dannenberg, Eva-Marta Lundell

Publication date: 11 March 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.08.028

zbMATH Keywords

dynamic programmingapproximation algorithmphylogenetic treerooted tripletsmooth polynomial integer program

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• New heuristics for rooted triplet consistency
• 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
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions