Convex recoloring of paths

DOI10.1016/J.DAM.2013.02.034MaRDI QIDQ2448880zbMATH OpenOpenAlexFDO

Authors Karla Roberta Lima, Yoshiko Wakabayashi

Publication date 5 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.02.034

zbMATH Keywords

approximation algorithmconvex recoloringinteger linear programming

Mathematics Subject Classification ID

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

Recommendations

• Convex recoloring of paths
• Improved approximation algorithm for convex recoloring of trees
• 1.5-approximation algorithm for the 2-convex recoloring problem
• Approximation and Online Algorithms
• Efficient approximation of convex recolorings

Cites work

• Algorithms and Data Structures
• Approximation and Online Algorithms
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex recoloring of paths
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Efficient approximation of convex recolorings
• The Complexity of Minimum Convex Coloring

Cited in

(15)

• 1.5-approximation algorithm for the 2-convex recoloring problem
• An extended formulation of the convex recoloring problem on a tree
• Column generation approach to the convex recoloring problem on a tree
• A GRASP for the convex recoloring problem in graphs
• Strong intractability results for generalized convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• 1.5-approximation algorithm for the 2-convex recoloring problem
• Convex recoloring of paths
• Quadratic Kernelization for Convex Recoloring of Trees
• The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
• STACS 2004
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Quadratic kernelization for convex recoloring of trees
• Integer programming models and polyhedral study for the geodesic classification problem on graphs

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 Q2448880)