A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
ACM Transactions on Algorithms · 31.10.2019 · 15 (4) · 1-28
DOI: 10.1145/3341599 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 04.10.2019. Verfasst von Christoph Hunkenschröder und 2 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 12 Literaturangaben.
Abstract (Originalsprache)
We present a factor 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.
Zitieren
APA
Hunkenschröder, 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), 1-28. https://doi.org/10.1145/3341599
Vancouver
Hunkenschröder C, Vempala S, Vetta A. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem. ACM Transactions on Algorithms. 2019;15(4):1-28. doi:10.1145/3341599
BibTeX
@article{Hunkenschrder2019,
author = {Hunkenschröder, Christoph and Vempala, Santosh and Vetta, Adrian},
title = {A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem},
journal = {ACM Transactions on Algorithms},
year = {2019},
volume = {15},
number = {4},
pages = {1--28},
doi = {10.1145/3341599}
}
EUVIMED