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

Guardado en:

Detalles Bibliográficos
Autores principales:	Malaguti, E., Méndez-Díaz, I., José Miranda-Bront, J., Zabala, P.
Formato:	JOUR
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:	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	todo:paper_00283045_v65_n4_p353_Malaguti
record_format	dspace
spelling	todo:paper_00283045_v65_n4_p353_Malaguti2023-10-03T14:38:45Z A branch-and-price algorithm for the (k,c)-coloring problem Malaguti, E. Méndez-Díaz, I. José Miranda-Bront, J. Zabala, P. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Malaguti, E. Méndez-Díaz, I. José Miranda-Bront, J. Zabala, P. 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.
format	JOUR
author	Malaguti, E. Méndez-Díaz, I. José Miranda-Bront, J. Zabala, P.
author_facet	Malaguti, E. Méndez-Díaz, I. José Miranda-Bront, J. Zabala, P.
author_sort	Malaguti, E.
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
url	http://hdl.handle.net/20.500.12110/paper_00283045_v65_n4_p353_Malaguti
work_keys_str_mv	AT malagutie abranchandpricealgorithmforthekccoloringproblem AT mendezdiazi abranchandpricealgorithmforthekccoloringproblem AT josemirandabrontj abranchandpricealgorithmforthekccoloringproblem AT zabalap abranchandpricealgorithmforthekccoloringproblem AT malagutie branchandpricealgorithmforthekccoloringproblem AT mendezdiazi branchandpricealgorithmforthekccoloringproblem AT josemirandabrontj branchandpricealgorithmforthekccoloringproblem AT zabalap branchandpricealgorithmforthekccoloringproblem
_version_	1807323758350827520

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

Ejemplares similares