Palabras clave
robust coloring
heuristics
coloración de grafos
coloración robusta
heurísticas
Cómo citar
Resumen
Sean G y Ḡ dos grafos complementarios. Dada una función de penalización en las aristas de Ḡ, la rigidez de una k-coloración de G se define como la suma de las penalizaciones en las aristas de Ḡ cuyos vértices incidentes son del mismo color. Con base en la definición anterior, el Problema de Coloración Robusta (PCR) se define como la búsqueda de la k-coloración de rigidez mı́nima. Este trabajo realiza un estudio comparativo de varias técnicas heurísticas: Recocido Simulado, GRASP, y Búsqueda Dispersa. Los resultados aquí presentados son los mejores obtenidos para el PCR.
Citas
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.