TCS+ talk

Wednesday April 25, 2018 10:00 AM

Distributed All-Pairs Shortest Paths, Exactly

Speaker: Danupon Nanongkai , KTH Royal Institute of Technology
Location: Annenberg 205

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.

Series TCS+ Talks

Contact: Bonnie Leung bjleung@caltech.edu