Computing Phylogenetic Roots with Bounded Degrees and Errors

DOI10.1137/S0097539701389154zbMath1053.68069OpenAlexW2039104371MaRDI QIDQ4706236

Guo-Hui Lin, Tao Jiang, Zhi-Zhong Chen

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701389154

zbMATH Keywords

NP-hardphylogenycomputational biologyefficient algorithmphylogenetic root

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Applications of design theory to circuits and networks (94C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Cluster graph modification problems, Pairwise Compatibility Graphs: A Survey, Computing phylogenetic roots with bounded degrees and errors is NP-complete, Recognizing k -Leaf Powers in Polynomial Time, for Constant k, A \(2k\) kernel for the cluster editing problem, The 3-Steiner Root Problem, Approximation algorithms for bounded degree phylogenetic roots, Parameterized Leaf Power Recognition via Embedding into Graph Products, Fixed-parameter enumerability of cluster editing and related problems, Clustering with partial information, Clustering with Partial Information, Cluster Editing: Kernelization Based on Edge Cuts, Characterizing star-PCGs, Closest 4-leaf power is fixed-parameter tractable, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, A more effective linear kernelization for cluster editing, On the threshold of intractability, Simplicial powers of graphs, A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers, Parameterized leaf power recognition via embedding into graph products, Clustering with qualitative information, Simplicial Powers of Graphs, Linear-time algorithms for tree root problems