A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem

DOI10.1016/j.ipl.2007.05.007zbMath1183.05085OpenAlexW1523101460MaRDI QIDQ2379996

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

zbMATH Keywords

graph algorithmsparameterized complexityconvex recoloring

Mathematics Subject Classification ID

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

Related Items (5)

1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Hardness and inapproximability of convex recoloring problems ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

Cites Work

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

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