Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle

Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto

Given a $k$-vertex-connected graph $G$ and a set $S$ of extra edges (links), the goal of the $k$-vertex-connectivity augmentation problem is to find a set $S^{\prime }\subseteq S$ of minim…