Approximation algorithms for minimum size 2-connectivity problems
We study some versions of the problem of finding the minimum size 2-connected subgraph. This problem is NP-hard (even on cubic planar graphs) and MAX SNP-hard. We show that the minimum 2-edge connected subgraph problem can be approximated to within \(4/3-\varepsilon\) for general graphs, improving upon the recent result of Vempala and Vetta. Better approximations are obtained for planar graphs and for cubic graphs. We also consider the generalization, where requirements of 1 or 2 edge or vertex disjoint paths are specified between every pair of vertices, and the aim is to find a minimum subgraph satisfying these requirements. We show that this problem can be approximated within 3/2, generalizing earlier results for 2-connectivity. We also analyse the classical local optimization heuristics. For cubic graphs, our results imply a new upper bound on the integrality gap of the linear programming formulation for the 2-edge connectivity problem. For the entire collection see [Zbl 0958.00036].
- Approximating minimum size \{1,2\}-connected networks
- Biconnectivity approximations and graph carvings
- Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
- An improved approximation algorithm for minimum size 2-edge connected spanning subgraphs
- A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
- Finding 2-edge connected spanning subgraphs.
- Approximating minimum size \{1,2\}-connected networks
- Pruning 2-connected graphs
- A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
- A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
- scientific article; zbMATH DE number 437534 (Why is no real title available?)
- Pruning 2-connected graphs
- scientific article; zbMATH DE number 2119646 (Why is no real title available?)
- Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
- Color-avoiding connected spanning subgraphs with minimum number of edges
- An approximation algorithm for minimum-cost vertex-connectivity problems
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
This page was built for publication: Approximation algorithms for minimum size 2-connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762522)
