| Título: |
Heuristics for the Robust Coloring Problem Heurísticas para el Problema de Coloracion Robusta |
| Autores: |
Gutiérrez Andrade, Miguel Ángel Lara Velázquez, Pedro López Bracho, Rafael Ramírez Rodríguez, Javier |
| Fecha: |
2011-03-18 2013-11-06 2013-11-06 2013-11-06 |
| Publicador: | Centro de Investigación en Matemática Pura y Aplicada (CIMPA) |
| Fuente: |
Ver documento Ver documento |
| Tipo: |
info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion |
| Tema: | |
| Descripción: |
Let $G$ and $\bar{G}$ be complementary graphs. Given a penalty function defined on the edges of $G$, we will say that the rigidity of a $k$-coloring of $G$ is the sum of the penalties of the edges of G 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. Sean $G$ y $\bar{G}$ dos grafos complementarios. Dada una función de penalización en las aristas de $G$, la rigidez de una $k$-coloración de $G& se define como la suma de las penalizaciones en las aristas de $G$ 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úqueda 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. |
| Idioma: | spa |