Algoritmos de aproximación para aumentar la vértice-conectividad de un ciclo

Abstract

Los problemas de aumentación de conectividad son un caso particular del Survivable Network Problem, que ha sido muy estudiado en las últimas décadas por sus aplicaciones en el diseño de redes robustas. Estos problemas tienen como entrada un grafo G, que es k-vértice-conexo (respectivamente arista-conexo) y un conjunto de links S, tal que G ∪ S es (k+1)-vértice-conexo (respectivamente arista-conexo), y consisten en encontrar el conjunto F ⊆ S de tamaño mínimo tal que G ∪ F es (k+1)-vértice-conexo. Sin embargo, la mayor parte de la investigación sobre problemas de aumentación realizada hasta ahora se ha centrado en el caso de arista-conectividad. En esta tesis nos enfocamos en encontrar algoritmos de aproximación para aumentar la vértice-conectividad de un ciclo de n vértices Cₙ, y logramos construir para todo ε > 0 un algoritmo de búsqueda local de complejidad n^O(1/ε) con un orden de aproximación cercano a 1.87029 + ε. Para conseguir esto se demuestran resultados novedosos relativos a la estructura de soluciones minimales. Además, se presenta una formulación como programa lineal y una demostración de que el problema es APX-difícil. Este trabajo se puede ver como una extensión de los resultados de Gálvez et al. para el caso en el que se aumenta la arista-conectividad de un ciclo. Nuestros resultados corresponden al primer paso para abordar el caso más general en el que se aumenta la conectividad de un grafo 2-vértice-conexo cualquiera, cuyo mejor orden de aproximación conocido es de 2.