ILP models and column generation for the minimum sum coloring problem

DOI10.1016/J.ENDM.2018.01.023zbMATH Open1388.05064OpenAlexW2789976508WikidataQ57659006 ScholiaQ57659006MaRDI QIDQ1742227FDOQ1742227

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

Publication date: 11 April 2018

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

Recommendations

• A branch-and-price algorithm for the minimum sum coloring problem
• Exact solution of graph coloring problems via constraint programming and column generation
• Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem
• New algorithm for the sum coloring problem
• Lower bounds for the minimal sum coloring problem

zbMATH Keywords

integer programminggraph coloringcolumn generation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
• Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem
• A column-generation approach to the multiple knapsack problem with color constraints
• On a binary-encoded ILP coloring formulation
• A branch-and-price algorithm for the minimum sum coloring problem

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

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