Título:  Sobre la thinness y thinness propia de un grafo
Directora: Flavia Bonomo
Jurados: Guillermo Durán y Esteban Feuerstein

Fecha: Miércoles 9 de Septiembre de 2020
Hora: 10 hs

La defensa va a ser en el aula 9 (virtual) del DC.

Resumen:
Los grafos con thinness acotada fueron denidos por Mannino, Oriolo, Ricci y Chandran como una generalización de los grafos de intervalos, con el propósito de desarrollar una heurística para el problema de asignación de frecuencias en redes GSM. En esta tesis introducimos el concepto de thinness propia, tal que los grafos con thinness propia acotada generalizan a los grafos de
intervalos propios. Estudiamos la complejidad computacional de problemas relacionados al reconocimiento de grafos con thinness y thinness propia acotada por k, demostrando que
algunos son NP-completos y otros polinomiales; aunque los problemas de reconocimiento siguen abiertos incluso para k = 2. El caso k = 1 corresponde a los grafos de intervalos y
de intervalos propios, respectivamente, y por lo tanto se reconocen en tiempo polinomial.
Describimos el comportamiento de la thinness y thinness propia bajo las operaciones de grafos unión, suma, y producto Cartesiano. Tambien estudiamos la relación entre ambos
parámetros con otros de la literatura como cutwidth, linear MIM-width, y anidamiento de intervalos, que complementan a resultados previos sobre boxicidad y pathwidth. Finalmente,
describimos una amplia familia de problemas que pueden resolverse con técnicas de programación dinámica en tiempo polinomial en grafos con thinness acotada, dada cierta representación, generalizando a la familia list matrix partition, y luego para grafos con thinness propia acotada la extendemos para incluir problemas de dominación y sus versiones pesadas.

Palabras clave: Grafo, Intervalos, Thinness, Complejidad, Algoritmo.