DRAFT
Caltech Logo

TCS+ Talk

Wednesday, April 25, 2018
10:00am to 11:00am
Add to Cal
Annenberg 205
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.

For more information, please contact Bonnie Leung by email at [email protected].