Fast 2-Approximate All-Pairs Shortest Paths
Fast 2-Approximate All-Pairs Shortest Paths
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ(n2.5-r + nω(r)) time, for any r ∈ [0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, …