2016/12/14 by Vishnu V. Narayan, Narayan, Vishnu V.
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1612.04790
We obtain a polynomial-time 17/12-approximation algorithm for the minimum-cost 2-vertex-connected spanning subgraph problem, restricted to graphs of minimum degree at least 3. Our algorithm uses the framework of ear-decompositions for approximating connectivity problems, which was previously used in algorithms for finding the smallest 2-edge-connected spanning subgraph by Cheriyan, Sebő and Szigeti (SIAM J.Discrete Math. 2001) who gave a 17/12-approximation algorithm for this problem, and by Sebő and Vygen (Combinatorica 2014), who improved the approximation ratio to 4/3.