We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G\w?", for any triple of vertices u, v,w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with n vertices in O(mnlog n) total time and O(n2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edgerelated queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(mnlog n) total time and O(n2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m+n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.

Georgiadis, L., Hansen, T.d., Italiano, G.f., Krinninger, S., Parotsidis, N. (2017). Decremental data structures for connectivity and dominators in directed graphs. In Leibniz International Proceedings in Informatics, LIPIcs: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ICALP.2017.42].

Decremental data structures for connectivity and dominators in directed graphs

Italiano, Giuseppe F.;
2017-01-01

Abstract

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G\w?", for any triple of vertices u, v,w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with n vertices in O(mnlog n) total time and O(n2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edgerelated queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(mnlog n) total time and O(n2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m+n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
pol
2017
AICA
Rilevanza internazionale
2017
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Decremental algorithms; Dominator tree; Dynamic graph algorithms; Strong connectivity under failures; Software
Article number 42
http://drops.dagstuhl.de/opus/institut_lipics.php?fakultaet=04
Intervento a convegno
Georgiadis, L., Hansen, T.d., Italiano, G.f., Krinninger, S., Parotsidis, N. (2017). Decremental data structures for connectivity and dominators in directed graphs. In Leibniz International Proceedings in Informatics, LIPIcs: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ICALP.2017.42].
Georgiadis, L; Hansen, Td; Italiano, Gf; Krinninger, S; Parotsidis, N
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/201108
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact