Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
verfasst von : Loukas Georgiadis, Giuseppe F. Italiano, Charis Papadopoulos, Nikos Parotsidis
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
be a strongly connected directed graph. We consider the following three problems, where we wish to compute the smallest strongly connected spanning subgraph of
G
that maintains respectively: the 2-edge-connected blocks of
G
(
2EC-B
); the 2-edge-connected components of
G
(
2EC-C
); both the 2-edge-connected blocks and the 2-edge-connected components of
G
(
2EC-B-C
). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For
2EC-C
we can obtain a 3/2-approximation by combining previously known results. For
2EC-B
and
2EC-B-C
, we present new 4-approximation algorithms that run in linear time. We also propose various heuristics to improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.