Two-connected spanning subgraphs with at most (10)/(7)OPT edges

2016/09/01 by Heeger, Klaus, Vygen, Jens
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1609.00147

Abstract

We present a (10)/(7)-approximation algorithm for the minimum two-vertex-connected spanning subgraph problem.

Related

• 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
• A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
• A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem
• A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
• A 5/4-Approximation for Two-Edge Connectivity