Wednesday, April 25, 2018
10:00 am
Annenberg 205

TCS+ talk

Distributed All-Pairs Shortest Paths, Exactly
Danupon Nanongkai , KTH Royal Institute of Technology

Abstract:  I will present the ~O(n^{5/4})-time distributed algorithm for computing all-pairs shortest paths exactly by Huang, Nanongkai, and Saranurak (FOCS 2017; https://arxiv.org/abs/1708.03903). The algorithm is fairly simple, and the talk will cover necessary backgrounds. I will also briefly survey recent progresses and some open problems in the field of distributed graph algorithms, where this work lies in.

Contact Bonnie Leung bjleung@caltech.edu
Add this event to my calendar