Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

Sunny Atalig, Alexander Hickerson, Arrdya Srivastav +2

We consider the classical single-source shortest path problem in directed weighted graphs. D.~Eppstein proved recently an $\hat{I}\text{c◯}(n^3)$ lower bound for oblivious algorithms that use re…