| Autor: |
Gutiérrez-Andrade, Miguel Ángel, Lara-Velázquez, Pedro, López-Bracho, Rafael, Ramírez-Rodríguez, Javier |
| Jazyk: |
angličtina |
| Rok vydání: |
2011 |
| Předmět: |
|
| Zdroj: |
Revista de Matemática Teoría y Aplicaciones, Volume: 18, Issue: 1, Pages: 137-139, Published: JUN 2011 |
| Popis: |
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 kcoloring. 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 Ḡ 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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
