A branch-and-price algorithm for the minimum sum coloring problem
From MaRDI portal
Publication:1983110
DOI10.1016/j.dam.2020.08.031zbMath1472.05049OpenAlexW3087024762MaRDI QIDQ1983110
Fabio Furini, Diego Delle Donne, Enrico Malaguti, Roberto Wolfler Calvo
Publication date: 15 September 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.08.031
column generationinteger linear programmingvertex coloringbranch-and-price algorithmminimum sum coloring
Integer programming (90C10) Linear programming (90C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- A memetic algorithm for the minimum sum coloring problem
- An exact approach for the vertex coloring problem
- A simple branching scheme for vertex coloring problems
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- On a graph partition problem with application to VLSI layout
- On the cost-chromatic number of graphs
- On chromatic sums and distributed resource allocation
- Hybrid evolutionary search for the minimum sum coloring problem of graphs
- ILP models and column generation for the minimum sum coloring problem
- An effective heuristic algorithm for sum coloring of graphs
- On sum coloring of graphs
- Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Minimal coloring and strength of graphs
- Computing lower bounds for minimum sum coloring and optimum cost chromatic partition
- A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
- On the asymmetric representatives formulation for the vertex coloring problem
- Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
- AN EXTRACTION AND EXPANSION APPROACH 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
- A Column Generation Approach for Graph Coloring
- On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
- A Primer in Column Generation
- Benchmarking optimization software with performance profiles.
