A 5/4-Approximation for Two-Edge Connectivity
Open Access
- 15 June 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 653-664
Abstract
No abstract availableAll Related Versions
Funding Information
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021_200731 \/ 1)
- CSR Grant (WMGT-23-0001)
This publication has 35 references indexed in Scilit:
- A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem2022
- On the Cycle Augmentation Problem: Hardness and Approximation AlgorithmsTheory of Computing Systems, 2021
- On the Tree Augmentation ProblemAlgorithmica, 2020
- The matching augmentation problem: a $\frac{7}{4}$-approximation algorithmMathematical Programming, 2019
- Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part IIAlgorithmica, 2017
- Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAPAlgorithmica, 2017
- 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 subgraphsCombinatorica, 2014
- Approximating the smallest k‐edge connected spanning subgraph by LP‐roundingNetworks, 2008
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph ProblemJournal of Algorithms, 1998