Motivated by the emergence of large-scale networks in today's applications, we show how to compute efficiently smaller subgraphs that maintain some properties of an input graph. In particular, let G be a strongly connected directed graph. We consider the problem of computing the smallest strongly connected spanning subgraph of G that maintains certain connectivity relations of G. Specifically, for 2-edge-connectivity, we consider how to maintain the maximal 2-edge-connected subgraphs (2ECS) or the 2-edge-connected components (2ECC) of G, or both the maximal 2-edge-connected subgraphs and the 2-edge-connected components (2EC). Similarly, for 2-vertex-connectivity, we consider how to maintain the maximal 2-vertex-connected subgraphs (2VCS) or the 2-vertex-connected components (2VCC) of G, or both the maximal 2-vertex-connected subgraphs and the 2-vertex-connected components (2VC). All those problems are NP-hard, and thus we are interested in approximation algorithms. Additionally, we aim at designing algorithms with a good practical performance, so that they are able to scale effectively to very large graphs. While for 2ECS and 2VCS one can obtain an approximation ratio smaller than 2 by combining previously known results, providing good approximations for the 2-edge and the 2-vertex-components case seems more challenging. Here, we present linear-time approximation algorithms that achieve the following approximation guarantees: • 4-approximation for 2ECC and 2EC, and• 6-approximation for 2VCC and 2VC.Also, augmented versions of our 2VCC algorithm computes a 6-approximation for maintaining both the 2-edge and the 2-vertex-connected components (2CC), and for maintaining all the 2-connectivity relations of G (2C), i.e., both the 2-edge and the 2-vertex-connected subgraphs and components. Moreover, we provide heuristics that 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., Karanasiou, A., Papadopoulos, C., & Parotsidis, N. (2017). Sparse certificates for 2-connectivity in directed graphs. THEORETICAL COMPUTER SCIENCE, 698, 40-66 [10.1016/j.tcs.2017.06.015].
|Tipologia:||Articolo su rivista|
|Citazione:||Georgiadis, L., Italiano, G.f., Karanasiou, A., Papadopoulos, C., & Parotsidis, N. (2017). Sparse certificates for 2-connectivity in directed graphs. THEORETICAL COMPUTER SCIENCE, 698, 40-66 [10.1016/j.tcs.2017.06.015].|
|IF:||Con Impact Factor ISI|
|Settore Scientifico Disciplinare:||Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni|
|Revisione (peer review):||Esperti anonimi|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.tcs.2017.06.015|
|Stato di pubblicazione:||Pubblicato|
|Data di pubblicazione:||2017|
|Titolo:||Sparse certificates for 2-connectivity in directed graphs|
|Autori:||Georgiadis, L; Italiano, Gf; Karanasiou, A; Papadopoulos, C; Parotsidis, N|
|Appare nelle tipologie:||01 - Articolo su rivista|