Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)

Michael Elkin, Idan Shabat

Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\ge 1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n,k)$, that given a query $(u,…