Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
From MaRDI portal
Publication:2706198
DOI10.1137/S0895480199362071zbMath0972.05028MaRDI QIDQ2706198
András Sebő, Zoltán Szigeti, Joseph Cheriyan
Publication date: 19 March 2001
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (8)
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 ⋮ Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges ⋮ A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in 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 ⋮ How to Secure Matchings against Edge Failures ⋮ How to Secure Matchings Against Edge Failures
This page was built for publication: Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
