A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges

DOI10.1016/j.dam.2015.10.014zbMath1339.05260OpenAlexW2300052872MaRDI QIDQ298954

Yao Fu, Sylvia Boyd, Yu Sun

Publication date: 21 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.014

zbMATH Keywords

approximation algorithmintegrality gapcirculationsminimum 2-edge-connected subgraph problemsubcubic graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

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 Spanning Subgraph ⋮ A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

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
• Finding 2-edge connected spanning subgraphs.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• Biconnectivity approximations and graph carvings
• Approximating Graphic TSP by Matchings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges