ILP models and column generation for the minimum sum coloring problem

DOI10.1016/j.endm.2018.01.023zbMath1388.05064OpenAlexW2789976508WikidataQ57659006 ScholiaQ57659006MaRDI QIDQ1742227

Fabio Furini, Ian-Christopher Ternier, Enrico Malaguti, Sébastien Martin

Publication date: 11 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2018.01.023

zbMATH Keywords

integer programmingcolumn generationgraph coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)

Related Items (2)

A branch-and-price algorithm for the minimum sum coloring problem ⋮ A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints

Cites Work

• A memetic algorithm for the minimum sum coloring problem
• On a graph partition problem with application to VLSI layout
• On the cost-chromatic number of graphs
• Hybrid evolutionary search for the minimum sum coloring problem of graphs
• An effective heuristic algorithm for sum coloring of graphs
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• On sum coloring of graphs
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Lower Bounds for the Minimal Sum Coloring Problem
• A survey on vertex coloring problems
• Tight bounds on the chromatic sum of a connected graph
• Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
• A Column Generation Approach for Graph Coloring

This page was built for publication: ILP models and column generation for the minimum sum coloring problem