Convex recoloring of paths

DOI10.1016/J.ENDM.2011.05.029MaRDI QIDQ2840702zbMATH OpenOpenAlexFDO

Authors Karla Roberta Lima, Yoshiko Wakabayashi

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

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

Recommendations

• Convex recoloring of paths
• The convex recoloring problem: polyhedra, facets and computational experiments
• Improved approximation algorithm for convex recoloring of trees
• 1.5-approximation algorithm for the 2-convex recoloring problem
• Approximation and Online Algorithms

Cites work

• Approximation and Online Algorithms
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Efficient approximation of convex recolorings
• The Complexity of Minimum Convex Coloring

Cited in

(11)

• Column generation approach to the convex recoloring problem on a tree
• STACS 2004
• Convex recoloring of paths
• Quadratic kernelization for convex recoloring of trees
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• An extended formulation of the convex recoloring problem on a tree
• Quadratic Kernelization for Convex Recoloring of Trees
• 1.5-approximation algorithm for the 2-convex recoloring problem
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• The convex recoloring problem: polyhedra, facets and computational experiments
• 1.5-approximation algorithm for the 2-convex recoloring problem

This page was built for publication: Convex recoloring of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840702)