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

DOI10.1016/J.TCS.2006.06.016MaRDI QIDQ860811zbMATHOpenAlexFDO

Authors 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

Problems related to evolution (92D15) Trees (05C05) 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)

Recommendations

• Computing and Combinatorics
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• scientific article; zbMATH DE number 1830750
• Approximation algorithms for bounded degree phylogenetic roots
• scientific article; zbMATH DE number 1088267

Cites work

• scientific article; zbMATH DE number 1617253 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• Algorithms and Computation
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Graph-Theoretic Concepts in Computer Science
• On the completeness of a generalized matching problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Tree Powers

Cited in

(7)

• On the existence of funneled orientations for classes of rooted phylogenetic networks
• Closest 4-leaf power is fixed-parameter tractable
• A survey on pairwise compatibility graphs
• The Complexity of Rooted Phylogeny Problems
• Computing and Combinatorics
• Computing and Combinatorics
• Approximation algorithms for bounded degree phylogenetic roots

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q860811)