Defensa Tesis Licenciatura Francisco Laborda
Detalles del evento
Cuándo
de 15:00 a 16:00
Dónde
- Título: "Un algoritmo Branch & Bound combinatorio para el problema de coloreo de suma mínima en grafos P4-sparse"
- Directores: Dra. Flavia Bonomo y Dr. Javier Marenco
- Jurados: Dra. Paula Zabala (UBA), Dr. Mario Valencia-Pabon (Université Paris-Nord)
- Resumen:
El problema de Coloreo de Suma Mínima consiste en asignar números naturales a los vértices de un grafo de modo tal que pares de vértices adyacentes obtengan diferentes números, y la suma de los números asignados sea mínima. Un grafo es P4-sparse si todo conjunto de 5 vértices induce a lo sumo un P4. Además, los grafos P4-sparse tienen asociado un árbol de descomposición modular con raíz compuesto por operaciones básicas en los nodos y ciertos grafos primitivos en las hojas. Actualmente, no se conoce un algoritmo polinomial que resuelva el problema de coloreo de suma mínima en dicha clase, pero sí existe un algoritmo 2-aproximado, que retorna una solución cuya suma es a lo sumo el doble de la óptima.
En este trabajo, introducimos una familia de cotas inferiores para el problema y presentamos un algoritmo del estilo Branch & Bound combinatorio, el cual encuentra la solución óptima rápidamente para la mayoría de los casos.
