Efficient approximation of convex recolorings

DOI10.1016/j.jcss.2007.03.006zbMath1123.68095OpenAlexW2111929782MaRDI 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 algorithmsphylogenetic treesconvex recoloringlocal ratio technique

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (17)

Sharp upper and lower bounds on a restricted class of convex characters ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ 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 ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Heuristics for the connected assignment problem in arrays ⋮ The complexity of minimum convex coloring ⋮ Quadratic kernelization for convex recoloring of trees ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Convex recoloring of paths ⋮ On the complexity of generalized chromatic polynomials ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ 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
• 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

This page was built for publication: Efficient approximation of convex recolorings