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; 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
Add this event to my calendar