EADS Talk by Thomas Dueholm Hansen

On 15 August 2017, Thomas Dueholm Hansen, Assistant professor at the Department of Computer Science Aarhus University, will give an EADS talk at DIKU.

Decremental Single-Source Reachability and Strongly Connected Components in \tilde{O}(m\sqrt{n}) Total Update Time

We present randomized algorithms with a total update time of \tilde{O}(m\sqrt{n}) for the problems of decremental single-source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler.

Joint work with Shiri Chechik, Giuseppe F. Italiano, Jakub Łącki, and Nikos Parotsidis.