Let (Formula presented.) be a directed graph. A vertex (Formula presented.) (respectively an edge (Formula presented.)) is a strong articulation point (respectively a strong bridge) if its removal increases the number of strongly connected components of (Formula presented.). We implement and engineer fast algorithms for computing all the strong articulation points and all the strong bridges of a directed graph, based on the linear-time algorithms presented in Italiano et al. (Theor Comput Sci 447:74–84, 2012). Our implementations are tested against real-world graphs taken from several application domains, including social networks, communication graphs, web graphs, peer2peer networks and product co-purchase graphs. The algorithms implemented turn out to be very efficient in practice, and are able to run on large scale graphs, i.e., on graphs with ten million vertices and half billion edges. Our experiments on such graphs highlight some properties of strong articulation points, which might be of independent interest.

Firmani, D., Georgiadis, L., Italiano Giuseppe, F., Laura, L., Santaroni, F. (2016). Strong Articulation Points and Strong Bridges in Large Scale Graphs. ALGORITHMICA, 74(3), 1123-1147 [10.1007/s00453-015-9991-z].

Strong Articulation Points and Strong Bridges in Large Scale Graphs

Firmani Donatella;
2016-01-01

Abstract

Let (Formula presented.) be a directed graph. A vertex (Formula presented.) (respectively an edge (Formula presented.)) is a strong articulation point (respectively a strong bridge) if its removal increases the number of strongly connected components of (Formula presented.). We implement and engineer fast algorithms for computing all the strong articulation points and all the strong bridges of a directed graph, based on the linear-time algorithms presented in Italiano et al. (Theor Comput Sci 447:74–84, 2012). Our implementations are tested against real-world graphs taken from several application domains, including social networks, communication graphs, web graphs, peer2peer networks and product co-purchase graphs. The algorithms implemented turn out to be very efficient in practice, and are able to run on large scale graphs, i.e., on graphs with ten million vertices and half billion edges. Our experiments on such graphs highlight some properties of strong articulation points, which might be of independent interest.
2016
Firmani, D., Georgiadis, L., Italiano Giuseppe, F., Laura, L., Santaroni, F. (2016). Strong Articulation Points and Strong Bridges in Large Scale Graphs. ALGORITHMICA, 74(3), 1123-1147 [10.1007/s00453-015-9991-z].
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/11590/355760
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact