Heuristics for the Robust Coloring Problem

Fecha

2011-03-18 00:00:00

Tipo

artículo original

Autores

Gutiérrez Andrade, Miguel Ángel
Lara Velázquez, Pedro
Lopez Bracho, Rafael
Ramírez Rodríguez, Javier

Título de la revista

ISSN de la revista

Título del volumen

Editor

Resumen

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 y dos grafos complementarios. Dada una función de penalización en las aristas de , la rigidez de una -coloración de(Error rendering LaTeX formula)(Error rendering LaTeX formula)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.

Descripción

Palabras clave