Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Heuristics for the robust coloring problem
PDF (Español (España))

Keywords

graph coloring
robust coloring
heuristics
coloración de grafos
coloración robusta
heurísticas

How to Cite

Gutiérrez-Andrade, M. Ángel, Lara-Velázquez, P., Lopez-Bracho, R., & Ramírez-Rodríguez, J. (2011). Heuristics for the robust coloring problem. Revista De Matemática: Teoría Y Aplicaciones, 18(1), 137–148. https://doi.org/10.15517/rmta.v18i1.2119

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.

https://doi.org/10.15517/rmta.v18i1.2119
PDF (Español (España))

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.

Comments

Downloads

Download data is not yet available.