Convex recolorings of strings and trees: Definitions, hardness results and algorithms

DOI10.1016/j.jcss.2007.10.003zbMath1160.68025OpenAlexW2029029999MaRDI QIDQ931727

Sagi Snir, Shlomo Moran

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.10.003

zbMATH Keywords

complexityalgorithmsdynamic programmingfixed parameter tractabilityphylogenetics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A GRASP for the convex recoloring problem in graphs ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability of generalized convex recoloring problems ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Strong inequalities and a branch-and-price algorithm for the convex recoloring problem ⋮ Structured proportional representation ⋮ A strong formulation for the graph partition problem ⋮ A heuristic for the convex recoloring problem in graphs ⋮ Heuristics for the connected assignment problem in arrays ⋮ The complexity of minimum convex coloring ⋮ Quadratic kernelization for convex recoloring of trees ⋮ The parameterized complexity of some minimum label problems ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Combinatorial optimization in system configuration design ⋮ Convex Recoloring of Paths ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convex tree realizations of partitions
• The complexity of reconstructing trees from qualitative characters and subtrees
• Minimal Mutation Trees of Sequences
• Inferring Evolutionary History From DNA Sequences
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• A Polynomial-Time Algorithm for Near-Perfect Phylogeny
• Selecting the branches for an evolutionary tree.
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• Two strikes against perfect phylogeny
• Efficient algorithms for inferring evolutionary trees
• Minimizing phylogenetic number to find good evolutionary trees