Finding 2-edge connected spanning subgraphs

Finding 2-edge connected spanning subgraphs

0.00 Avg rating—0 Votes
Article ID: iaor20043259
Country: Netherlands
Volume: 32
Issue: 3
Start Page Number: 212
End Page Number: 216
Publication Date: May 2004
Journal: Operations Research Letters
Authors:
Abstract:

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|-|V|)/(r-1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximate guarantees of 5/4, 4/3, 11/8 and 7/5, respectively.

Reviews

Required fields are marked *. Your email address will not be published.