Incremental Strong Connectivity and 2-Connectivity in Directed Graphs - Archive ouverte HAL Access content directly
Conference Papers Year :

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.
Fichier principal
Vignette du fichier
1802.10189.pdf (2.43 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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

Collections

INRIA INRIA2
24 View
42 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More