Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves

Descargar versión PDF

Profesores: Dr. Pedro Lara VelázquezDr. Miguel Ángel Gutiérrez Andrade

Resumen: La coloración de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignación de frecuencias en problemas de telecomunicación; asignación de registros en un sistema operativo, programación de tareas; entre otras. La coloración de grafos se presenta en una gran variedad de formas de las cuales, la Coloración de Gráficas Suaves (CGS) es considerada una generalización del problema de coloración de gráficas.  El problema de Coloración de Gráficas Suaves se ha utilizado recientemente en problemas de clasificación y de reconocimiento de patrones en general. En este problema tenemos que, dada una gráfica con ponderaciones en las aristas, el objetivo es encontrar una coloración que minimice la suma de las aristas con el mismo color en ambos extremos; es decir, la suma de las penalizaciones denominada dureza. Asimismo, existen otros parámetros importantes en la Coloración de Gráficas Suaves como lo son la solidez, la cual proporciona un valor promedio de las penalizaciones de la gráfica y resilencia que permite encontrar una cantidad adecuada de colores. Es sabido que este problema es del tipo NP-duro y es necesario el uso de metaheurísticas en instancias mayores a 20 vértices.

Objetivo general

  • Desarrollar un algoritmo que resuelva varios problemas clásicos de coloración utilizando el enfoque de coloración de gráficas suaves

Objetivos específicos

  • Realizar un estudio del estado del arte de los problemas de coloración clásicos, así como su representación como gráfica suave
  • Compilación de instancias benchmark clásicas de cada uno de los problemas que se estudiarán
  • Desarrollo de los algoritmos de solución
  • Análisis de resultados y conclusiones

Última actualización: June 3, 2016 at 0:53 am

Búsqueda dispersa para el problema de coloración de gráficas suaves
Distribución de contenidos P2P en redes MANET utilizando conocimiento de redes sociales

Regresar a Proyectos de Investigación para alumnos de Maestría

P C y T I