This event has been cancelled
Decremental Single-Source Reachability and Strongly Connected Components in ~O(m \sqrt{n}) Total Update Time
Speaker
Shiri Chechik
Host
Virginia Vassilevska Williams
MIT CSAIL
Computing strongly connected components is one of the fundamental problems of graph algorithms.
The goal of *dynamic* strongly connected components (SCC) is to maintain the strongly connected components of a graph as the edges of the graph change over time.
The most general case is the fully dynamic one, where each adversarial update inserts or deletes an arbitrary edge. The trivial algorithm is to recompute SCC after every update in O(m) time. For the fully dynamic case, no non-trivial algorithm is known.
We can, however, improve upon the trivial algorithm by restricting the update sequence to be partially dynamic: only insertions (referred to as incremental), or only deletions (referred to as decremental).
In this talk I will present randomized algorithms with a total update time of ~O(m sqrt{n}) for the decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15].
Based on joint work with Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis.
The goal of *dynamic* strongly connected components (SCC) is to maintain the strongly connected components of a graph as the edges of the graph change over time.
The most general case is the fully dynamic one, where each adversarial update inserts or deletes an arbitrary edge. The trivial algorithm is to recompute SCC after every update in O(m) time. For the fully dynamic case, no non-trivial algorithm is known.
We can, however, improve upon the trivial algorithm by restricting the update sequence to be partially dynamic: only insertions (referred to as incremental), or only deletions (referred to as decremental).
In this talk I will present randomized algorithms with a total update time of ~O(m sqrt{n}) for the decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15].
Based on joint work with Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis.