Improved Distance (Sensitivity) Oracles with Subquadratic Space

Davide Bilò, Shiri Chechik, Keerti Choudhary +3

A distance oracle (DO) with stretch $(\alpha ,\beta )$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$, returns a value $\hat{d}(s,t)$ such that $d(s,t)…