Efficient approximation of convex recolorings

DOI10.1016/j.jcss.2007.03.006zbMath1123.68095MaRDI QIDQ2643731

Shlomo Moran, Sagi Snir

Publication date: 27 August 2007

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.03.006

zbMATH Keywords

approximation algorithms; phylogenetic trees; convex recoloring; local ratio technique

Mathematics Subject Classification ID

05C05: Trees

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

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

The convex recoloring problem: polyhedra, facets and computational experiments, The complexity of minimum convex coloring, Quadratic kernelization for convex recoloring of trees, On the complexity of generalized chromatic polynomials, 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, Sharp upper and lower bounds on a restricted class of convex characters, Strong intractability results for generalized convex recoloring problems, Strong intractability of generalized convex recoloring problems, Hardness and inapproximability of convex recoloring problems, Convex recoloring of paths, Strong inequalities and a branch-and-price algorithm for the convex recoloring problem, Convex Recoloring of Paths, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Connection Matrices for MSOL-Definable Structural Invariants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non deterministic polynomial optimization problems and their approximations
• Convex tree realizations of partitions
• The complexity of reconstructing trees from qualitative characters and subtrees
• One for the price of two: a unified approach for approximating covering problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• 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
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• Two strikes against perfect phylogeny
• Algorithms and Data Structures
• Efficient algorithms for inferring evolutionary trees
• Minimizing phylogenetic number to find good evolutionary trees