Defensa de Tesis de Maestría en Investigación de Operaciones de la Lic. Natalia Castro.
Tesis titulada: "Análisis y estudio de Complejidad del Problema de Fragmentación de Grafos".
Directores de tesis: Franco Robledo, Pablo Romero
Fecha: lunes 5 de Marzo de 2018 a las 14:00 horas.
Lugar: Salón Azul, 5o piso, Facultad de Ingeniería, UDELAR.
Tribunal:
Dra. Simone de Lima Martins - Universidad Federal Fluminense, Brasil.
Dr. Gerardo Rubino - Directeur de Recherche, INRIA, Francia.
Dr. Ing. Claudio Risso - Dpto. de Investigación Operativa, InCo, FING.
Resumen:
El objeto de estudio de esta tesis es un problema de optimización combinatoria, denominado
Problema de Fragmentación de Grafos (GFP). Inspirado por el modelado de epidemias
su aplicación puede extenderse a otras clases de desastres, por ejemplo, catástrofes naturales.
En esta tesis se estudia el Problema de Fragmentación de Grafos desde el punto de vista de
sus propiedades teóricas.
El sistema que será afectado se modela como una red, donde un nodo expuesto al desastre
inmediatamente lo propaga a sus vecinos. El objetivo del GFP es elegir una estrategia de
inmunización de forma en que se minimice el número esperado de muertes causadas. Se
presenta el problema mostrando además su relación con el modelo de epidemias clásico SIR
y con otro problema teórico de grafo denominado Component Order Connectivity problem.
Se prueba que el problema de decisión asociado al GFP pertenece a la clase de problemas
N P-completos y también un resultado fuerte de inaproximabilidad que muestra que no
existe un algoritmo aproximado de tiempo polinomial para la resolución del GFP con factor
menor a 5/3-\epsilon para cualquier \epsilon > 0, a menos que P =NP.
Por último en contraste con el anterior resultado de inaproximabilidad se hallan estrategias
de tiempo polinomial para la mejor inmunización en algunas familias especiales de
grafos, a saber, ciclos, grafos acíclicos y grafos bipartitos.
Palabras Clave: Problema de Fragmentación de Grafos, complejidad computacional, algoritmos
de aproximación.