2-Vertex Connectivity in Directed Graphs - Archive ouverte HAL Access content directly
Journal Articles Information and Computation Year : 2018

2-Vertex Connectivity in Directed Graphs

(1) , (2) , (3) , (1)
1
2
3

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. We are also able to compute in linear time a sparse certificate for 2-vertex connectivity, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-vertex connectivity properties as the input graph.
Fichier principal
Vignette du fichier
georgiadisetal-1.pdf (584.81 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01925966 , version 1 (18-11-2018)

Identifiers

Cite

Loukas Georgiadis, Giuseppe F Italiano, Luigi Laura, Nikos Parotsidis. 2-Vertex Connectivity in Directed Graphs. Information and Computation, 2018. ⟨hal-01925966⟩
8 View
275 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More