Let G be a strongly connected directed graph. We consider the problem of computing the smallest strongly connected spanning subgraph of G that maintains the pairwise 2-vertex-connectivity of G, i.e., the 2-vertex-connected blocks of G (2VC-B). We provide linear-time approximation algorithms for this problem that achieve an approximation ratio of 6. Based on these algorithms, we show how to approximate, in linear time, within a factor of 6 the smallest strongly connected spanning subgraph of G that maintains respectively: both the 2-vertexconnected blocks and the 2-vertex-connected components of G (2VC-BC); all the 2-connectivity relations of G (2C), i.e., both the 2-vertexand the 2-edge-connected components and blocks. 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., Karanasiou, A., Papadopoulos, C., Parotsidis, N. (2016). Sparse subgraphs for 2-connectivity in directed graphs. In Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) (pp.150-166). Springer Verlag [10.1007/978-3-319-38851-9_11].

Sparse subgraphs for 2-connectivity in directed graphs

Italiano, GF;Parotsidis, N
2016-01-01

Abstract

Let G be a strongly connected directed graph. We consider the problem of computing the smallest strongly connected spanning subgraph of G that maintains the pairwise 2-vertex-connectivity of G, i.e., the 2-vertex-connected blocks of G (2VC-B). We provide linear-time approximation algorithms for this problem that achieve an approximation ratio of 6. Based on these algorithms, we show how to approximate, in linear time, within a factor of 6 the smallest strongly connected spanning subgraph of G that maintains respectively: both the 2-vertexconnected blocks and the 2-vertex-connected components of G (2VC-BC); all the 2-connectivity relations of G (2C), i.e., both the 2-vertexand the 2-edge-connected components and blocks. 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.
International symposium on experimental algorithms, 15. (SEA 2016)
rus
2016
Rilevanza internazionale
2016
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Theoretical Computer Science; Computer Science (all)
http://springerlink.com/content/0302-9743/copyright/2005/
Intervento a convegno
Georgiadis, L., Italiano, G., Karanasiou, A., Papadopoulos, C., Parotsidis, N. (2016). Sparse subgraphs for 2-connectivity in directed graphs. In Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics) (pp.150-166). Springer Verlag [10.1007/978-3-319-38851-9_11].
Georgiadis, L; Italiano, G; Karanasiou, A; Papadopoulos, C; Parotsidis, N
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/201142
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact