Convex Recoloring of Paths
From MaRDI portal
Publication:2840702
DOI10.1016/j.endm.2011.05.029zbMath1268.05142OpenAlexW2036848684MaRDI QIDQ2840702
Yoshiko Wakabayashi, Karla Roberta Lima
Publication date: 23 July 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.029
approximation algorithmconvex coloringconvex recoloring problemCRPconvex recoloring on pathsinteger linear formulation
Integer programming (90C10) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)
Related Items
Convex recoloring of paths, The convex recoloring problem: polyhedra, facets and computational experiments
Cites Work
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
- Efficient approximation of convex recolorings
- The Complexity of Minimum Convex Coloring
- Connected Coloring Completion for General Graphs: Algorithms and Complexity
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- Approximation and Online Algorithms