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.
Georgiadis, L., Italiano, G.f., Papadopoulos, C., Parotsidis, N. (2015). Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs. In Procedings 23rd Annual European Symposium (pp.582-594). Springer Verlag [10.1007/978-3-662-48350-3_49].
Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
ITALIANO, GIUSEPPE FRANCESCO;
2015-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
