New fixed-parameter algorithms for the minimum quartet inconsistency problem

DOI10.1007/s00224-009-9165-yzbMath1204.68257OpenAlexW2050473290MaRDI QIDQ1959377

Maw-Shang Chang, Peter Rossmanith, Chuang-Chieh Lin

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9165-y

zbMATH Keywords

evolutionary treefixed-parameter algorithmleaf-labeled treedepth-bounded search treeminimum quartet inconsistency problemquartet topology

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Reconstructing phylogenetic trees from multipartite quartet systems ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ A property tester for tree-likeness of quartet topologies ⋮ Testing consistency of quartet topologies: a parameterized approach ⋮ On the weighted quartet consensus problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors
• Mathematics for the analysis of algorithms.
• The complexity of reconstructing trees from qualitative characters and subtrees
• A general method to speed up fixed-parameter-tractable algorithms
• A fixed-parameter algorithm for minimum quartet inconsistency
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• A few logs suffice to build (almost) all trees (I)

This page was built for publication: New fixed-parameter algorithms for the minimum quartet inconsistency problem