Convex Recoloring of Paths

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

zbMATH Keywords

approximation algorithmconvex coloringconvex recoloring problemCRPconvex recoloring on pathsinteger linear formulation

Mathematics Subject Classification ID

Integer programming (90C10) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (2)

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

This page was built for publication: Convex Recoloring of Paths