Convex Recoloring Revisited: Complexity and Exact Algorithms

DOI10.1007/978-3-642-02882-3_39MaRDI QIDQ5323087zbMATH OpenOpenAlexFDO

Authors Dieter Kratsch, Iyad 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

convex leaf recoloringconvex path recoloringconvex tree recoloringindependent set problemproblem complexity

Mathematics Subject Classification ID

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

Recommendations

• Convex recoloring of paths
• Convex recoloring of paths
• On the complexity of solving or approximating convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• 1.5-approximation algorithm for the 2-convex recoloring problem

Cites work

• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Algorithmic graph theory and perfect graphs
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• scientific article; zbMATH DE number 3708461 (Why is no real title available?)
• Improved approximation algorithm for convex recoloring of trees
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Measure and conquer
• On powers of chordal graphs and their colorings
• Quadratic Kernelization for Convex Recoloring of Trees
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems

Cited in

(19)

• 1.5-approximation algorithm for the 2-convex recoloring problem
• An extended formulation of the convex recoloring problem on a tree
• Strong intractability results for generalized convex recoloring problems
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Strong intractability of generalized convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• Convex recoloring of paths
• The convex recoloring problem: polyhedra, facets and computational experiments
• Efficient approximation of convex recolorings
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• Convex recoloring of paths
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• The complexity of minimum convex coloring
• The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation and Online Algorithms
• Heuristics for the connected assignment problem in arrays

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323087)