1.5-approximation algorithm for the 2-convex recoloring problem
From MaRDI portal
Publication:1647830
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
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