Keywords
robust coloring
heuristics
coloración de grafos
coloración robusta
heurísticas
How to Cite
Abstract
Let G and Ḡ be complementary graphs. Given a penalty function defined on the edges of Ḡ, we will say that the rigidity of a k-coloring of G is the sum of the penalties of the edges of Ḡ joining vertices of the same color. Based on the previous definition, the Robust Coloring Problem (RCP) is stated as the search of the minimum rigidity k-coloring. In this work a comparison of heuristics based on simulated annealing, GRASP and scatter search is presented. These are the best results for the RCP that have been obtained.
References
Chams, M.; Hertz, A.; de Werra, D. (1987) “Some experiments with simulated annealing for coloring graphs”, European Journal of Operational Research 32: 260–266.
Feo, T.A.; Resende, M. (1995) “Greedy randomized adaptive search procedures”, Journal of Global Optimization 6: 109–134.
Glover, F.; Laguna, M. (1997) Tabu Search. Kluwer Academic Publishers, Boston.
Glover, F. (1998) “A template for scatter search and path relinking in artificial evolution”, in: J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer & D. Snyers (Eds.) Lecture Notes in Computer Science 1363, Springer, Heidelberg: 13–54.
Johnson, D.S.; Aragon, C.R.; McGeoch, L.A.; Schevon. C. (1991) “Optimization by simulated annealing: an experimental evaluation. Part II: graph coloring and number partitioning”, Operations Research 39(3): 378–406.
Ramı́rez-Rodríguez, J. (2001) Extensiones del problema de coloración de grafos. Tesis Doctoral, Universidad Complutense de Madrid, Madrid. Disponible en: http://eprints.ucm.es/4479/
Yáñez, J.; Ramı́rez, J. (2003) “The robust coloring problem”, European Journal of Operational Research 148(3): 546–558.