Graph connectivity is a fundamental concept in graph theory with numerous practical applications. Very recently, various notions of 2-connectivity in directed graphs (digraphs) have been introduced. In particular, 2-connectivity revealed to have a much richer and more complicated structure in directed graphs than in undirected graphs. In this paper we consider the computation of the 2-connected components and the 2-connected blocks of a digraph in practice, in the case of both edge and vertex connectivity. Specifically, we present efficient implementations of previously proposed and of new algorithms for computing the 2-vertex-connected components and the 2-vertex-connected blocks, the 2-edge-connected components and the 2-edge-connected blocks, and evaluate their performance experimentally on large digraphs taken from a variety of application areas. To the best of our knowledge, this is the first empirical study for these problems. Our extensive experimental study sheds light on the relative difficulty of computing these notions of 2-connectivity in digraphs in practice. Furthermore, our experimental results suggest that the 2-vertex- and 2-edge-connected components of digraphs that arise in many practical applications can be found efficiently, despite the fact that currently the best known asymptotical bound for their computation is O(mn).

Di Luigi, W., Georgiadis, L., Italiano, G.f., Laura, L., Parotsidis, N. (2015). 2-Connectivity in directed graphs: an experimental study. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA [http://dx.doi.org/10.1137/1.9781611973754.15].

2-Connectivity in directed graphs: an experimental study

ITALIANO, GIUSEPPE FRANCESCO;
2015-01-01

Abstract

Graph connectivity is a fundamental concept in graph theory with numerous practical applications. Very recently, various notions of 2-connectivity in directed graphs (digraphs) have been introduced. In particular, 2-connectivity revealed to have a much richer and more complicated structure in directed graphs than in undirected graphs. In this paper we consider the computation of the 2-connected components and the 2-connected blocks of a digraph in practice, in the case of both edge and vertex connectivity. Specifically, we present efficient implementations of previously proposed and of new algorithms for computing the 2-vertex-connected components and the 2-vertex-connected blocks, the 2-edge-connected components and the 2-edge-connected blocks, and evaluate their performance experimentally on large digraphs taken from a variety of application areas. To the best of our knowledge, this is the first empirical study for these problems. Our extensive experimental study sheds light on the relative difficulty of computing these notions of 2-connectivity in digraphs in practice. Furthermore, our experimental results suggest that the 2-vertex- and 2-edge-connected components of digraphs that arise in many practical applications can be found efficiently, despite the fact that currently the best known asymptotical bound for their computation is O(mn).
17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015
San Diego, CA, USA
2015
Rilevanza internazionale
2015
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Intervento a convegno
Di Luigi, W., Georgiadis, L., Italiano, G.f., Laura, L., Parotsidis, N. (2015). 2-Connectivity in directed graphs: an experimental study. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA [http://dx.doi.org/10.1137/1.9781611973754.15].
Di Luigi, W; Georgiadis, L; Italiano, Gf; Laura, L; 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/115636
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact