Convex Recoloring Revisited: Complexity and Exact Algorithms

DOI10.1007/978-3-642-02882-3_39zbMath1248.05201OpenAlexW1568993744MaRDI QIDQ5323087

Dieter Kratsch, Iyad A. Kanj

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_39

zbMATH Keywords

independent set problemproblem complexityconvex leaf recoloringconvex path recoloringconvex tree recoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

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 ⋮ Heuristics for the connected assignment problem in arrays ⋮ The complexity of minimum convex coloring ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Convex recoloring of paths ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ Convex Recoloring of Paths ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

Cites Work

• Maximum weight independent sets and cliques in intersection graphs of filaments
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Algorithmic graph theory and perfect graphs
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Measure and conquer
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Quadratic Kernelization for Convex Recoloring of Trees
• Unnamed Item
• Unnamed Item

This page was built for publication: Convex Recoloring Revisited: Complexity and Exact Algorithms