Diseño e implementación de un algoritmo GRASP para el problema de coloración de grafos

Resumen

Una  de  las  dificultades  en  la  búsqueda  de  la  solución  óptima  a  problemas  de  optimización  combinatoria  es  el  elevado  costo  computacional para obtenerlas. Por ello se hace necesaria  la utilización de algoritmos basados en metaheurísticas para obtener  soluciones  factibles a un costo computacional razonable. En este contexto,  en el presente trabajo se aborda el diseño de una heurística basada en la metodología  GRASP  para  el  Problema  de  Coloración  de  Grafos.  Este  algoritmo  se  lo  ha  implementado  en Mathematica  8.0.4.0  ®  y  ejecutado con diversas  instancias del problema para  medir  la calidad del mismo.