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

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