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

DOI10.1137/16M1057486zbMath1362.05069OpenAlexW2600683609MaRDI QIDQ5346544

Philippe Legault, Sylvia Boyd

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)

Related Items (6)

A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ 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 ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ Unnamed Item ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

Cites Work

• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• 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 factor 2 approximation algorithm for the generalized Steiner network problem
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph