Loading...
research article
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
October 1, 2019
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.
Type
research article
Web of Science ID
WOS:000496745500011
Authors
Publication date
2019-10-01
Published in
Volume
15
Issue
4
Start page
55
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 29, 2019
Use this identifier to reference this record