Skip to Main content Skip to Navigation
Journal articles

2-Vertex Connectivity in Directed Graphs

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01925966
Contributor : Marie-France Sagot <>
Submitted on : Sunday, November 18, 2018 - 4:42:13 PM
Last modification on : Monday, November 19, 2018 - 11:13:59 AM
Long-term archiving on: : Tuesday, February 19, 2019 - 12:43:01 PM

File

georgiadisetal-1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01925966, version 1
  • ARXIV : 1409.6277

Citation

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

Share

Metrics

Record views

51

Files downloads

432