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
Descripción
Sumario: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.

Ejemplares similares