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.
Type de document :
Communication dans un congrès
Latin American Symposium on Theoretical Informatics, 2018, Buenos Aires, Argentina
Liste complète des métadonnées

https://hal.inria.fr/hal-01925953
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 18 novembre 2018 - 16:20:43
Dernière modification le : mardi 20 novembre 2018 - 01:17:53

Fichier

1802.10189.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

8

Téléchargements de fichiers

10