Skip to Main content Skip to Navigation
Conference papers

Incremental Strong Connectivity and 2-Connectivity in Directed Graphs

Abstract : In this paper, we present new incremental algorithms for maintaining data structures that represent all connectivity cuts of size one in directed graphs (digraphs), and the strongly connected components that result by the removal of each of those cuts. We give a conditional lower bound that provides evidence that our algorithms may be tight up to a sub-polynomial factors. As an additional result, with our approach we can also maintain dynamically the 2-vertex-connected components of a digraph during any sequence of edge insertions in a total of O(mn) time. This matches the bounds for the incremental maintenance of the 2-edge-connected components of a digraph.
Document type :
Conference papers
Complete list of metadata
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Sunday, November 18, 2018 - 4:20:43 PM
Last modification on : Tuesday, November 20, 2018 - 1:17:53 AM
Long-term archiving on: : Tuesday, February 19, 2019 - 12:48:26 PM


Files produced by the author(s)


  • HAL Id : hal-01925953, version 1
  • ARXIV : 1802.10189



Loukas Georgiadis, Giuseppe Italiano, Nikos Parotsidis. Incremental Strong Connectivity and 2-Connectivity in Directed Graphs. Latin American Symposium on Theoretical Informatics, 2018, Buenos Aires, Argentina. ⟨hal-01925953⟩



Record views


Files downloads