On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

For an undirected unweighted graph G = (V, E) with n vertices and m edges, let d(u, v) denote the distance from u in V to v in V in G. An (alpha, beta)-stretch approximate distance…