Heuristics for the robust coloring problem

dc.creatorGutiérrez-Andrade,Miguel Ángel
dc.creatorLara-Velázquez,Pedro
dc.creatorLópez-Bracho,Rafael
dc.creatorRamírez-Rodríguez,Javier
dc.date2011-06-01
dc.date.accessioned2023-09-25T14:02:38Z
dc.date.available2023-09-25T14:02:38Z
dc.identifierhttp://www.scielo.sa.cr/scielo.php?script=sci_arttext&pid=S1409-24332011000100010
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/8811267
dc.descriptionLet 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.
dc.formattext/html
dc.languageen
dc.publisherCentro de Investigaciones en Matemática Pura y Aplicada (CIMPA) y Escuela de Matemática, San José, Costa Rica.
dc.rightsinfo:eu-repo/semantics/openAccess
dc.sourceRevista de Matemática Teoría y Aplicaciones v.18 n.1 2011
dc.subjectgraph coloring
dc.subjectrobust coloring
dc.subjectheuristics
dc.titleHeuristics for the robust coloring problem
dc.typeinfo:eu-repo/semantics/article


Este ítem pertenece a la siguiente institución