A branch-and-price algorithm for the minimum sum coloring problem
type: Item
instance of: scholarly article
title: A branch-and-price algorithm for the minimum sum coloring problem
zbMATH Open document ID: 1472.05049
author: Diego Delle Donne
author: Fabio Furini
author: Enrico Malaguti
author: Roberto Wolfler Calvo
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 7395726
zbMATH Keywords: minimum sum coloring
zbMATH Keywords: vertex coloring
zbMATH Keywords: integer linear programming
zbMATH Keywords: column generation
zbMATH Keywords: branch-and-price algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2020.08.031
OpenAlex ID: W3087024762
cites work: On chromatic sums and distributed resource allocation
cites work: On the asymmetric representatives formulation for the vertex coloring problem
cites work: A Primer in Column Generation
cites work: Benchmarking optimization software with performance profiles.
cites work: ILP models and column generation for the minimum sum coloring problem
cites work: Exact solution of graph coloring problems via constraint programming and column generation
cites work: A simple branching scheme for vertex coloring problems
cites work: Minimal coloring and strength of graphs
cites work: Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
cites work: Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
cites work: Maximum-weight stable sets and safe lower bounds for graph coloring
cites work: Hybrid evolutionary search for the minimum sum coloring problem of graphs
cites work: A memetic algorithm for the minimum sum coloring problem
cites work: Computing lower bounds for minimum sum coloring and optimum cost chromatic partition
cites work: An exact approach for the vertex coloring problem
cites work: A survey on vertex coloring problems
cites work: A Column Generation Approach for Graph Coloring
cites work: A polyhedral approach for graph coloring
cites work: On the cost-chromatic number of graphs
cites work: Lower bounds for the minimal sum coloring problem
cites work: A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
cites work: On sum coloring of graphs
cites work: On a graph partition problem with application to VLSI layout
cites work: Tight bounds on the chromatic sum of a connected graph
cites work: On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
cites work: An effective heuristic algorithm for sum coloring of graphs
cites work: An extraction and expansion approach for graph coloring
DOI: 10.1016/J.DAM.2020.08.031
description: scientific article; zbMATH DE number 7395726