Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
Finding a minimum size spanning 2-edge-connected subgraph in a 2-edge-connected graph is NP-hard as the Hamiltonian cycle problem is a special case of this problem. It is easy to find a spanning 2-edge-connected subgraph with no more than twice the optimum number of edges: simply find an ear-decomposition of \(G\) and leave out all the trivial ears (those that are just an edge). Khuller and Vishkin gave a 1.5-approximation algorithm for the problem based on depth-first search. In the current paper the authors give a \({17\over 12}\)-approximation algorithm for the problem based on a result of A. Frank on the minimum number of even ears in an ear-decomposition of a 2-edge-connected graph. Recently Vempala and Vetta have improved the best approximation guarantee to \({4\over 3}\) [\textit{S. Vempala} and \textit{A. Vetta}, Factor \({4\over 3}\) approximations for minimum 2-connected subgraphs, in Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Max-Plank-Institut für Informatik, Saarbrücken, Germany; Springer, Berlin, 262-273 (2000)].
- scientific article; zbMATH DE number 1187147
- Finding 2-edge connected spanning subgraphs.
- A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
- Biconnectivity approximations and graph carvings
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Finding 2-edge connected spanning subgraphs.
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
- A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
- A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
- A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
- Minimum 2-edge connected spanning subgraph of certain graphs
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- scientific article; zbMATH DE number 1187147 (Why is no real title available?)
- An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
- scientific article; zbMATH DE number 2119647 (Why is no real title available?)
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- scientific article; zbMATH DE number 1405676 (Why is no real title available?)
- A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
- How to Secure Matchings Against Edge Failures
- How to Secure Matchings against Edge Failures
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges
- Approximation and Online Algorithms
- Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
- A 4/3 approximation for 2-vertex-connectivity
- An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
- A PTAS for weighted triangle-free 2-matching
- Approximation schemes for planar graph connectivity problems
This page was built for publication: Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706198)
