Theory Seminar

Distributed Exact Weighted All-Pairs Shortest Paths

Yi-Jun Chang

Graduate Student
University of Michigan
Friday, September 29, 2017
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

A fundamental question in distributed computing is how fast a network can compute shortest paths. This question has been extensively studied in the CONGEST model, where a network is modeled by an n-vertex m-edge graph. Each vertex represents a processor. The communication proceeds in synchronized rounds, with an O(log n)-bit message size constraint.

In this talk, I will present a STOCཌྷ paper (by Huang, Nanongkai, and Saranurak, arXiv:1708.03903), which shows an O(n^{5/4} poly log n)-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse.

Additional Information

Sponsor(s): CSE

Open to: Public