A 2O(k)poly(n) algorithm for the parameterized convex recoloring problem

DOI10.1016/J.IPL.2007.05.007zbMATH Open1183.05085OpenAlexW1523101460MaRDI QIDQ2379996FDOQ2379996

Authors: Igor Razgon 

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.05.007

Recommendations

• Convex Recoloring Revisited: Complexity and Exact Algorithms
• 1.5-approximation algorithm for the 2-convex recoloring problem
• 1.5-approximation algorithm for the 2-convex recoloring problem
• On the complexity of solving or approximating convex recoloring problems
• The convex recoloring problem: polyhedra, facets and computational experiments
• Efficient approximation of convex recolorings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Hardness and inapproximability of convex recoloring problems
• A heuristic for the convex recoloring problem in graphs
• A GRASP for the convex recoloring problem in graphs

zbMATH Keywords

graph algorithmsparameterized complexityconvex recoloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Algorithms and Data Structures
• Quadratic Kernelization for Convex Recoloring of Trees

Cited In (10)

• The convex recoloring problem: polyhedra, facets and computational experiments
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Quadratic kernelization for convex recoloring of trees
• Quadratic Kernelization for Convex Recoloring of Trees
• 1.5-approximation algorithm for the 2-convex recoloring problem
• A kernel for convex recoloring of weighted forests
• Hardness and inapproximability of convex recoloring problems
• Efficient approximation of convex recolorings
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems

This page was built for publication: A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem

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