Unique Perfect Phylogeny Is NP-Hard

DOI10.1007/978-3-642-21458-5_13zbMath1339.68104arXiv1011.5737OpenAlexW2146459540MaRDI QIDQ3011849

Juraj Stacho, Michel A. Habib

Publication date: 29 June 2011

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

Full work available at URL: https://arxiv.org/abs/1011.5737

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
• The complexity of reconstructing trees from qualitative characters and subtrees
• An idealized concept of the true cladistic character
• A mathematical foundation for the analysis of cladistic character compatibility
• An algebraic analysis of cladistic characters
• A characterization for a set of partial partitions to define an \(X\)-tree
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Complexity of generalized satisfiability counting problems
• Unique perfect phylogeny is intractable
• Competitive graph searches
• Triangulating 3-Colored Graphs
• Complexity and algorithms for reasoning about time
• Triangulating Vertex-Colored Graphs
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• Algorithmic Aspects of Tree Amalgamation
• Graph Sandwich Problems
• Efficient algorithms for inferring evolutionary trees

This page was built for publication: Unique Perfect Phylogeny Is NP-Hard