Two-connected spanning subgraphs with at most 107OPT edges

DOI10.1137/16M1091587MaRDI QIDQ5351864zbMATH OpenOpenAlexFDO

Authors Klaus Heeger, Jens Vygen

Publication date 31 August 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.00147

zbMATH Keywords

approximation algorithmear-decompositionvertex-connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: We present a $frac107$-approximation algorithm for the minimum two-vertex-connected spanning subgraph problem.

Recommendations

• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• scientific article; zbMATH DE number 1187147

Cites work

• Approximating k-Connected m-Dominating Sets
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• Biconnectivity approximations and graph carvings
• Conservative weightings and ear-decompositions of graphs
• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• scientific article; zbMATH DE number 437534 (Why is no real title available?)
• scientific article; zbMATH DE number 1305417 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• scientific article; zbMATH DE number 871896 (Why is no real title available?)
• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• Non-Separable and Planar Graphs
• 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

Cited in

(7)

• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
• A 4/3 approximation for 2-vertex-connectivity
• Survivable network design with group-to-group requirement
• A PTAS for weighted triangle-free 2-matching
• A proof of unimodality on the numbers of connected spanning subgraphs in an \(n\)-vertex graph with at least \(\left\lceil (3-2\sqrt 2) n^2 + n - \frac {7-2\sqrt 2}{2 \sqrt 2}\right\rceil\) edges

This page was built for publication: Two-connected spanning subgraphs with at most \(\frac{10}{7}{\mathrm{OPT}}\) edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351864)