Sesión Matemática DiscretaComplejidad computacional de algunos problemas de modificación a grafos de intervalos.
Aldana Ayelén Alcantar
UBA-Instituto de cálculo, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Un problema de modificación de grafos consiste en analizar cómo agregar o borrar aristas o vértices de forma mínima para que el grafo resultante cumpla una cierta propiedad. En particular, el problema $\Pi$-$Completion$ consiste en agregar aristas de forma mínima para que el grafo cumpla la propiedad deseada $\Pi$. La complejidad computacional de estos problemas suele ser difícil por lo que se busca encontrar versiones tratables modificando la clase de grafos que se utiliza como input.
En este trabajo, buscamos analizar la complejidad del problema de completar grafos de línea arco circulares a grafos de intervalos. Específicamente, queremos determinar si un grafo de línea arco circular $L(G)$ puede ser completado con $k$ o menos aristas para convertirse en un grafo de intervalos, y demostrar que esto es equivalente a encontrar un OLA de tamaño específico en $L(G)$.
Este trabajo es una primera aproximación a analizar la complejidad del problema de completar grafos arco circulares a grafos de intervalos, el cual es un problema abierto.
Trabajo en conjunto con: Guillermo Durán (UBA, FCEN, Departamento de Matemática. CONICET- Instituto de Cálculo (IC). Buenos Aires, Argentina). y Nina Pardal (UBA, FCEN, Departamento de Computación. CONICET- Instituto de Ciencias de la Computación (ICC ). Buenos Aires, Argentina. University of Sheffield, Inglaterra).