1.5-approximation algorithm for the 2-convex recoloring problem

DOI10.1016/j.dam.2017.01.008zbMath1390.05061OpenAlexW2588663527MaRDI QIDQ1647830

Gilad Kutiel, Dror Rawitz, Reuven Bar Yehuda

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.01.008

zbMATH Keywords

approximation algorithmsgreedyconvex recoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (2)

Strong intractability results for generalized convex recoloring problems ⋮ Strong inequalities and a branch-and-price algorithm for the convex recoloring problem

Cites Work

• The complexity of minimum convex coloring
• Quadratic kernelization for convex recoloring of trees
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Convex recoloring of paths
• Efficient approximation of convex recolorings
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Solving or Approximating Convex Recoloring Problems
• Convex Recoloring Revisited: Complexity and Exact Algorithms

This page was built for publication: 1.5-approximation algorithm for the 2-convex recoloring problem