Speaker: Shiri Chechik

Date: Tuesday, October 03, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type: Seminar

Room Description:

Host: Virginia Vassilevska Williams, MIT CSAIL

Contact: Nardos Abbay, nardos@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Decremental Single-Source Reachability and Strongly Connected Components in ~O(m \sqrt{n}) Total Update Time

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.

Research Areas:
None selected

Impact Areas:
None selected

Created by Deborah Goodwin at Wednesday, September 20, 2017 at 5:32 PM.