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

DOI10.1016/j.jcss.2007.10.003zbMath1160.68025MaRDI 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

complexity; algorithms; dynamic programming; fixed parameter tractability; phylogenetics

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D15: Problems related to evolution

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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