A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

DOI10.1145/3341599zbMath1454.68184OpenAlexW2979731478WikidataQ127112599 ScholiaQ127112599MaRDI QIDQ4973051

Christoph Hunkenschröder, Adrian Vetta, Santosh Vempala

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3341599

zbMATH Keywords

graph connectivityapproximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (6)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem ⋮ Approximation algorithms for flexible graph connectivity ⋮ Color-avoiding connected spanning subgraphs with minimum number of edges ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree

This page was built for publication: A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem