Computing phylogenetic roots with bounded degrees and errors is NP-complete

DOI10.1016/j.tcs.2006.06.016zbMath1153.68383OpenAlexW2011633748MaRDI QIDQ860811

Tatsuie Tsukiji, Zhi-Zhong Chen

Publication date: 9 January 2007

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

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

zbMATH Keywords

phylogenycomputational biologyNP-hardnessphylogenetic root

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Approximation algorithms for bounded degree phylogenetic roots ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ A survey on pairwise compatibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Tree Powers
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation

This page was built for publication: Computing phylogenetic roots with bounded degrees and errors is NP-complete