Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares

Los resultados de esta tesis se enmarcan dentro del área de la Optimización Combinatoria. Principalmente, se conjugan técnicas asociadas a las áreas de Complejidad Computacional, Algoritmos y Teoría de Grafos, entre otras. Se exponen los resultados obtenidos luego del estudio de la complejidad computacional para cada número entero positivo k fijo, de las siguientes variantes del problema clásico de dominación en grafos en algunas subclases de los grafos arco-circulares: k-upla dominación, k-dominación y k-dominación total. Para k = 1, todas ellas coinciden con el concepto usual de dominación, 1-dominación o dominación total en grafos. Desde el punto de vista de la complejidad computacional de problemas de decisión, estas variantes de la dominación clásica son "difíciles” de resolver. Como es habitual, se planteó entonces estudiar subclases donde los problemas sean tratables, es decir, resolubles a través de un algoritmo eficiente (de tiempo de ejecución u orden polinomial en el tamano de las instancias). Se investigaron instancias dadas por clases de grafos para los cuales existen en la literatura algoritmos que resuelven el problema para k = 1 en tiempo polinomial y que su tratamiento estaba abierto para los restantes valores de k enteros o bien, que disponen de un tal algoritmo pero el mismo es poco eficiente en algún sentido. Si bien los problemas abordados generalizan los diferentes conceptos de dominación, los algortimos que presentamos en esta tesis no son una generalización de los existentes en la literatura para el problema de dominación usual. Aún notando que la diferencia en las definiciones de los problemas estudiados es muy sutil, la estructura intrínseca de cada clase de grafos abordada mostró que en general no es sencillo, o bien no es posible, aplicar el mismo tratamiento a las tres variantes del problema estudiado en esas clases. Más precisamente, en esta tesis se desarrollan: para la k-dominación y k-dominación total y sus versiones ponderadas, un algoritmo específico de orden polinomial en función de k para la clase de los grafos de intervalos propios; para la k-upla dominación, sendos algoritmos eficientes para dos subclases de grafos arco-circulares, la de los grafos co-biconvexos y la de los grafos web, instancias para las que no se contaba hasta el momento con un algoritmo de resolución.