Nikos Parotsidis: Decremental Single-Source Reachability and Strongly Connected Components
Speaker:
Nikos Parotsidis, University of Rome Tor Vergata
Data dell'evento:
Wednesday, 8 November, 2017 - 12:00
Luogo:
Room A4@DIAG, via Ariosto 25, ground floor
Contatto:
leonardi@dis.uniroma1.it
We present randomized algorithms with a total update time of 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. In this talk, we are going to briefly review the Las Vegas algorithm by Roditty and Zwick [SICOMP 08] and the algorithm by Łącki [TALG 13], both with a total update time O(mn) (expected time in the case of the algorithm by Roditty and Zwick). Our algorithms carefully combine these two results, along with new structural properties, including a separation lemma in the case of graphs with a large diameter.
(Appeared in FOCS 2016. Joint work with Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, and Jakub Łącki.)
(Appeared in FOCS 2016. Joint work with Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, and Jakub Łącki.)