info:eu-repo/semantics/article
A tabu search heuristic for the equitable coloring problem
Fecha
2014-03Registro en:
Méndez-díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; A tabu search heuristic for the equitable coloring problem; Springer-v D I Verlag Gmbh; Lecture Notes in Computer Science; 8596; 3-2014; 347-358
0302-9743
CONICET Digital
CONICET
Autor
Méndez-díaz, Isabel
Nasini, Graciela Leonor
Severin, Daniel Esteban
Resumen
The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances.