A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
2019
Résumé
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.
Détails
Titre
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
Auteur(s)
Hunkenschroeder, Christoph ; Vempala, Santosh ; Vetta, Adrian
Publié dans
Acm Transactions On Algorithms
Volume
15
Numéro
4
Pages
55
Date
2019-10-01
ISSN
1549-6325
1549-6333
1549-6333
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
DISOPT
Le document apparaît dans
Production scientifique et compétences > SB - Faculté des sciences de base > MATH - Institut de mathématiques > DISOPT - Chaire d'optimisation discrète
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Production scientifique et compétences > SB - Faculté des sciences de base > Mathématiques
Publications validées par des pairs
Travail produit à l'EPFL
Articles de journaux
Publié
Date de création de la notice
2019-11-29