Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams +1

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in $n^{3-o(1)}$ time, and it is widely open whether it has an $O(n^{3-\epsilon })$ time algori…