Título: Técnicas de programación lineal entera para el problema de coloreo de aristas de grafos cúbicos

Directores: Brian Curcio, Isabel Méndez Díaz y Paula Zabala

Jurados: Santiago Figueira y Federico Pousa

Resumen:

En este trabajo de tesis se estudia en detalle un esquema de programación lineal entera para resolver el problema del coloreo propio de aristas de grafos 3-regulares. La técnica fue introducida por G. L. Nemhauser y S. Park, y consiste en una estrategia de generación de columnas integrada a un algoritmo de planos de corte. Se implementa el esquema presentado por los autores, proponiendo variaciones propias a la técnica. Luego, se generan conjuntos de instancias con los cuales se lleva a cabo una experimentación con el objetivo de evaluar el desempeño del método. De esta forma, se obtiene la combinación óptima de sus parámetros y estrategias para luego compararla con otras formulaciones del problema existentes en la literatura. Por último, se presentan resultados y observaciones sobre extensiones teóricas y prácticas del esquema propuesto.