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

DOI10.1016/J.TCS.2006.06.016zbMATH Open1153.68383OpenAlexW2011633748MaRDI QIDQ860811FDOQ860811

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

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

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)

Cites Work

• The Planar Hamiltonian Circuit Problem is NP-Complete
• On the completeness of a generalized matching problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tree Powers
• Title not available (Why is that?)
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science

Cited In (6)

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

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)