Heuristics for the robust coloring problem

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:
Bibliographic Details
Main Authors: Gutiérrez-Andrade,Miguel Ángel, Lara-Velázquez,Pedro, López-Bracho,Rafael, Ramírez-Rodríguez,Javier
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!

Similar Items

Similar Items