On the Complexity of Solving or Approximating Convex Recoloring Problems

DOI10.1007/978-3-642-38768-5_54zbMath1382.68100OpenAlexW132016661MaRDI QIDQ4925275

Cristiana Huiban, Rudini Menezes Sampaio, Yoshiko Wakabayashi, Manoel B. Campêlo

Publication date: 11 June 2013

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-38768-5_54

zbMATH Keywords

polynomial algorithmNP-hardnessinapproximabilitygrid graphsparse graphcographconvex recoloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

1.5-approximation algorithm for the 2-convex recoloring problem ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ A heuristic for the convex recoloring problem in graphs ⋮ Hardness and inapproximability of convex recoloring problems ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

This page was built for publication: On the Complexity of Solving or Approximating Convex Recoloring Problems