Heuristics for the robust coloring problem
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.
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Centro de Investigaciones en Matemática Pura y Aplicada (CIMPA) y Escuela de Matemática, San José, Costa Rica.
2011
|
| Online Access: | http://www.scielo.sa.cr/scielo.php?script=sci_arttext&pid=S1409-24332011000100010 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|