Heurísticas para el problema de coloración robusta
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...
| Main Authors: | , , , |
|---|---|
| Format: | Online |
| Language: | spa |
| Published: |
Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
2011
|
| Online Access: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/2119 |
| Summary: | 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. |
|---|