A branch-and-price algorithm for the (k,c)-coloring problem

In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop...

Descripción completa

Detalles Bibliográficos
Autores principales: Méndez Díaz, Isabel, Zabala, Paula
Publicado: 2015
Materias:
branch-and-price
column generation
computational experiments
frequency assignment
heuristics
multicoloring
vertex coloring
Coloring
Costs
Integer programming
Linear programming
Branch and price
Column generation
Computational experiment
Frequency assignments
Multicoloring
Vertex coloring
Algorithms
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00283045_v65_n4_p353_Malaguti
http://hdl.handle.net/20.500.12110/paper_00283045_v65_n4_p353_Malaguti
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00283045_v65_n4_p353_Malaguti
record_format dspace
spelling paper:paper_00283045_v65_n4_p353_Malaguti2023-06-08T14:54:56Z A branch-and-price algorithm for the (k,c)-coloring problem Méndez Díaz, Isabel Zabala, Paula branch-and-price column generation computational experiments frequency assignment heuristics multicoloring vertex coloring Coloring Costs Integer programming Linear programming Branch and price Column generation Computational experiment Frequency assignments heuristics Multicoloring Vertex coloring Algorithms In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop a Branch-and-Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for k and c, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails. © 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353-366 2015 © 2014 Wiley Periodicals, Inc. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00283045_v65_n4_p353_Malaguti http://hdl.handle.net/20.500.12110/paper_00283045_v65_n4_p353_Malaguti
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic branch-and-price
column generation
computational experiments
frequency assignment
heuristics
multicoloring
vertex coloring
Coloring
Costs
Integer programming
Linear programming
Branch and price
Column generation
Computational experiment
Frequency assignments
heuristics
Multicoloring
Vertex coloring
Algorithms
spellingShingle branch-and-price
column generation
computational experiments
frequency assignment
heuristics
multicoloring
vertex coloring
Coloring
Costs
Integer programming
Linear programming
Branch and price
Column generation
Computational experiment
Frequency assignments
heuristics
Multicoloring
Vertex coloring
Algorithms
Méndez Díaz, Isabel
Zabala, Paula
A branch-and-price algorithm for the (k,c)-coloring problem
topic_facet branch-and-price
column generation
computational experiments
frequency assignment
heuristics
multicoloring
vertex coloring
Coloring
Costs
Integer programming
Linear programming
Branch and price
Column generation
Computational experiment
Frequency assignments
heuristics
Multicoloring
Vertex coloring
Algorithms
description In this article, we study the (k,c)-coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)-coloring problem and develop a Branch-and-Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for k and c, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails. © 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353-366 2015 © 2014 Wiley Periodicals, Inc.
author Méndez Díaz, Isabel
Zabala, Paula
author_facet Méndez Díaz, Isabel
Zabala, Paula
author_sort Méndez Díaz, Isabel
title A branch-and-price algorithm for the (k,c)-coloring problem
title_short A branch-and-price algorithm for the (k,c)-coloring problem
title_full A branch-and-price algorithm for the (k,c)-coloring problem
title_fullStr A branch-and-price algorithm for the (k,c)-coloring problem
title_full_unstemmed A branch-and-price algorithm for the (k,c)-coloring problem
title_sort branch-and-price algorithm for the (k,c)-coloring problem
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00283045_v65_n4_p353_Malaguti
http://hdl.handle.net/20.500.12110/paper_00283045_v65_n4_p353_Malaguti
work_keys_str_mv AT mendezdiazisabel abranchandpricealgorithmforthekccoloringproblem
AT zabalapaula abranchandpricealgorithmforthekccoloringproblem
AT mendezdiazisabel branchandpricealgorithmforthekccoloringproblem
AT zabalapaula branchandpricealgorithmforthekccoloringproblem
_version_ 1768545222408536064

Ejemplares similares