Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges

DOI10.1137/16M1091587zbMath1369.05126arXiv1609.00147OpenAlexW2962808423MaRDI QIDQ5351864

Jens Vygen, Klaus Heeger

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

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

Related Items

Beating the Integrality Ratio for $s$-$t$-Tours in Graphs

Cites Work

• 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
• Conservative weightings and ear-decompositions of graphs
• Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• Biconnectivity approximations and graph carvings
• Non-Separable and Planar Graphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating k-Connected m-Dominating Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges