Computing Phylogenetic Roots with Bounded Degrees and Errors
From MaRDI portal
Publication:4706236
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
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