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; 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