Una comparación de modelos para un nuevo problema de coloreo

Resumen

El problema de coloreo de vértices consiste en asignar un
color a cada vértice de un grafo tal que vértices adyacentes reciban colores
distintos, utilizando la mínima cantidad de colores. Este problema ha sido
ampliamente estudiado.
En este trabajo, presentamos un problema al que llamamos Problema de
Coloreo de Vértices por Componentes Conexas (CCCP, por sus siglas
en inglés), que es una variación del problema de coloreo de vértices y
que, hasta donde sabemos, no ha sido denido ni estudiado previamente.
Después de demostrar varias propiedades, formalizamos su denición con
3 modelos de programación matemática. Obtenemos también cotas inferiores y superiores, que nos permiten eliminar variables de los modelos
originales. Además, diseñamos varias heurísticas para CCCP que permiten obtener soluciones iniciales.
Para comparar los rendimientos de los algoritmos basados en los modelos
propuestos, tanto respecto a la calidad de las soluciones encontradas así
como a los tiempos de ejecución, generamos un conjunto de instancias
y llevamos a cabo experimentación. Las conclusiones nos permiten comprender qué partes del algoritmo deberíamos mejorar y también concebir
nuevas formas de tratar nuestro problema.