Faster All-Pairs Optimal Electric Car Routing

Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2

We present a randomized $\tilde{O}(n^{3.5})$-time algorithm for computing \emph{optimal energetic paths} for an electric car between all pairs of vertices in an $n$-vertex directed…