A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem

DOI10.1016/j.tcs.2022.12.013OpenAlexW4311765316MaRDI QIDQ2680988

Ali Çivril

Publication date: 5 January 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.07232

zbMATH Keywords

combinatorial optimizationapproximation algorithmsminimum 2-edge-connected spanning subgraph problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Corrigendum to: ``A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem

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
• Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
• Biconnectivity approximations and graph carvings
• A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem