Búsqueda dispersa para el problema de coloración de gráficas suaves

Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El problema de coloración de gráficas suaves es una generalización del problema de coloración, en donde un grafo completo, las aristas tienen penalizaciones. Este problema se ha demostrado que puede resolver otros problemas tales como coloración mínima, coloración equitativa, entre otros; y en tiempos recientes, como parte de un trabajo de tesis de maestría, se ha demostrado su utilidad como clasificador no supervisado. Debido a que este modelo es del tipo NP-difícil, se requiere el uso de metaheurísticas para problemas con mas de 20 vértices. En este proyecto se propone realizar un algoritmo de solución utilizando la metaheurística de búsqueda dispersa.

Objetivo general

  • Desarrollar un algoritmo de solución para el problema de coloración de gráficas suaves utilizando la técnica metaheurística de búsqueda dispersa

Objetivos específicos

  • Revisión del estado del arte de problema a resolver y la técnica de solución
  • Planteamiento de instancias apropiadas para verificar la calidad del algoritmo
  • Propuesta de un algoritmo de solución
  • Implementación del algoritmo en C, FreeBASIC o Python, y su validación en las instancias de prueba seleccionadas anteriormente
  • Redacción de la idónea comunicación de resultados

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

Modelo adaptable de protocolos de comunicación y encaminamiento para el intercambio de información médica mediante dispositivos móviles inteligentes
Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves

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

P C y T I