Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph

DOI10.1137/16M1057486MaRDI QIDQ5346544zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmcubic graphsintegrality gapminimum cost 2-edge connected spanning subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Connectivity (05C40)

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

Cites work

• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Finding 2-factors closer to TSP tours in cubic graphs
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• 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

(9)

• scientific article; zbMATH DE number 7525493 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• 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)