Improved All-Pairs Approximate Shortest Paths in Congested Clique

Hong Duc Bui, Shashwat Chandra, Yi-Jun Chang +2

In this paper, we present a new randomized $O(1)$-approximation algorithm for the All-Pairs Shortest Paths (APSP) problem in weighted undirected graphs that runs in just $O(\log \l…