Incremental Strong Connectivity and 2-Connectivity in Directed Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Incremental Strong Connectivity and 2-Connectivity in Directed Graphs

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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
26 Consultations
63 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More