%0 Journal Article
%T Heuristics for the robust coloring problem
%A Guti¨¦rrez-Andrade
%A Miguel ¨¢ngel
%A Lara-Vel¨¢zquez
%A Pedro
%A L¨®pez-Bracho
%A Rafael
%A Ram¨ªrez-Rodr¨ªguez
%A Javier
%J Revista de Matem¨¢tica Teor¨ªa y Aplicaciones
%D 2011
%I Centro de Investigaciones en Matem¨¢tica Pura y Aplicada (CIMPA)
%X 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.
%K graph coloring
%K robust coloring
%K heuristics.
%U http://www.scielo.sa.cr/scielo.php?script=sci_abstract&pid=S1409-24332011000100010&lng=en&nrm=iso&tlng=en