Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
DOI10.1137/16M1057486zbMATH Open1362.05069OpenAlexW2600683609MaRDI QIDQ5346544FDOQ5346544
Authors: Sylvia Boyd, Philippe Legault 
Publication date: 24 May 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1057486
Recommendations
- Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
- scientific article; zbMATH DE number 1305417
- A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
- scientific article; zbMATH DE number 1187147
- Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
- 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 2079404
- Minimum cost \(\leq k\) edges connected subgraph problems
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
approximation algorithmcubic graphsintegrality gapminimum cost 2-edge connected spanning subgraph problem
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Connectivity (05C40)
Cites Work
- Finding 2-factors closer to TSP tours in cubic graphs
- Title not available (Why is that?)
- 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
- A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- Title not available (Why is that?)
- A factor 2 approximation algorithm for the generalized Steiner network problem
Cited In (9)
- Title not available (Why is that?)
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
- A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
- Title not available (Why is that?)
- Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
- Shorter tours and longer detours: uniform covers and a bit beyond
- Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
- Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
This page was built for publication: Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346544)
