Given a directed graph, two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. In this paper, we show how to compute this relation in O(m+n) time, where n is the number of vertices and m is the number of edges of the graph. As a side result, we show how to build in linear time an O(n)-space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices v and w are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from v to w or in all paths from w to v.

Georgiadis, L., Italiano, G., Laura, L., Parotsidis, N. (2018). 2-vertex connectivity in directed graphs. INFORMATION AND COMPUTATION, 261(2), 248-264 [10.1016/j.ic.2018.02.007].

2-vertex connectivity in directed graphs

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

Abstract

Given a directed graph, two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. In this paper, we show how to compute this relation in O(m+n) time, where n is the number of vertices and m is the number of edges of the graph. As a side result, we show how to build in linear time an O(n)-space data structure, which can answer in constant time queries on whether any two vertices are 2-vertex-connected. Additionally, when two query vertices v and w are not 2-vertex-connected, our data structure can produce in constant time a “witness” of this property, by exhibiting a vertex or an edge that is contained in all paths from v to w or in all paths from w to v.
2018
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Con Impact Factor ISI
Connectivity; directed graph; dominators; flow graph; strong articulation points; theoretical computer science; information systems; computer science applications1707; computer vision and pattern recognition; computational theory and mathematics
http://www.elsevier.com/inca/publications/store/6/2/2/8/4/4/index.htt
Georgiadis, L., Italiano, G., Laura, L., Parotsidis, N. (2018). 2-vertex connectivity in directed graphs. INFORMATION AND COMPUTATION, 261(2), 248-264 [10.1016/j.ic.2018.02.007].
Georgiadis, L; Italiano, G; Laura, L; Parotsidis, N
Articolo su rivista
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/201092
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 5
social impact