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

DOI10.1016/J.TCS.2022.12.013MaRDI QIDQ2680988zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• scientific article; zbMATH DE number 2079404
• scientific article; zbMATH DE number 1187147
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem

Cites work

• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• scientific article; zbMATH DE number 1688381 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• Biconnectivity approximations and graph carvings
• Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
• 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

(10)

• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• scientific article; zbMATH DE number 1187147 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• Approximation Algorithms for the Minimum Cardinality Two-Connected Spanning Subgraph Problem
• Corrigendum to: ``A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680988)