On the complexity of constructing evolutionary trees

DOI10.1023/A:1009833626004zbMath0957.90111OpenAlexW1559569263MaRDI QIDQ1306398

Andrzej Lingas, Leszek Gąsieniec, Anna Östlin, Jesper Jansson

Publication date: 21 November 1999

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009833626004

zbMATH Keywords

algorithmhomeomorphismtime complexityevolutionary treecensensus tree

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (16)

APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ Encoding and constructing 1-nested phylogenetic networks with trinets ⋮ Inferring a level-1 phylogenetic network from a dense set of rooted triplets ⋮ \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time ⋮ The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets ⋮ Building a small and informative phylogenetic supertree ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets ⋮ New heuristics for rooted triplet consistency ⋮ Maximum agreement and compatible supertrees ⋮ Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks ⋮ New results on optimizing rooted triplets consistency ⋮ Computing the maximum agreement of phylogenetic networks ⋮ Unnamed Item ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Faster exact computation of rSPR distance

This page was built for publication: On the complexity of constructing evolutionary trees