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
Heurísticas para el problema de coloración robusta
PDF

Palabras clave

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

Cómo citar

Gutiérrez-Andrade, M. Ángel, Lara-Velázquez, P., Lopez-Bracho, R., & Ramírez-Rodríguez, J. (2011). Heurísticas para el problema de coloración robusta. Revista De Matemática: Teoría Y Aplicaciones, 18(1), 137–148. https://doi.org/10.15517/rmta.v18i1.2119

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.

https://doi.org/10.15517/rmta.v18i1.2119
PDF

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.

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.