A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
2019
Abstract
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.
Details
Title
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
Author(s)
Hunkenschroeder, Christoph ; Vempala, Santosh ; Vetta, Adrian
Published in
Acm Transactions On Algorithms
Volume
15
Issue
4
Pages
55
Date
2019-10-01
ISSN
1549-6325
1549-6333
1549-6333
Keywords
Other identifier(s)
View record in Web of Science
Laboratories
DISOPT
Record Appears in
Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date
2019-11-29