A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approximation algorithm constructs a 2-edge connected spanning subgraph by modifying the smallest 2-edge cover.
Cite this item
Hunkenschroeder, C., Vempala, S., & Vetta, A. (2019). A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem. Acm Transactions on Algorithms, 15(4). https://doi.org/10.1145/3341599
Click Copy to copy the citation, or select the text manually.
WOS:000496745500011
2019-10-01
15
4
55
REVIEWED
EPFL