On the hardness of inferring phylogenies from triplet-dissimilarities

DOI10.1016/j.tcs.2007.07.048zbMath1143.68018OpenAlexW1969795126MaRDI QIDQ2465625

Shlomo Moran, Ilan Gronau

Publication date: 7 January 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.048

zbMATH Keywords

hardness of approximationphylogenetic treesNP hardnessdistance based reconstruction algorithms

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

The matroid structure of representative triple sets and triple-closure computation

Cites Work

• Computational complexity of inferring phylogenies from dissimilarity matrices
• The complexity of ultrametric partitions on graphs
• Low dimensional embeddings of ultrametrics.
• A robust model for finding optimal evolutionary tree
• A few logs suffice to build (almost) all trees. II
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• A few logs suffice to build (almost) all trees (I)

This page was built for publication: On the hardness of inferring phylogenies from triplet-dissimilarities