A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph

2023/05/09 by Ali Çivril, Çivril, Ali
#cs.DS

paper · pdf · doi:10.48550/arxiv.2305.05398

Abstract

We provide algorithms for the minimum 2-edge-connected spanning subgraph problem and the minimum 2-vertex-connected spanning subgraph problem with approximation ratio both (4)/(3). Using a common theme, the algorithms and their analyses are very similar.

Citations

• A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem

Related

• A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem
• 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
• A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3
• Two-connected spanning subgraphs with at most (10)/(7)OPT edges
• A 5/4-Approximation for Two-Edge Connectivity