Prof. Michael Elkin

In a seminal paper [27] for any n-vertex undirected graph G=(V E) and a parameter k 1, 2,. Thorup and Zwick constructed a distance oracle of size 0 (kn^1+1/k) which upon a query (u, v) constructs a path H between u and v of length δ (u, v) such that d_G (n, v) ≤δ (u, v) ≤ (2k-1)d_G (u, v). 'l'he query time of the oracle from [27] is O (k) (in addition to the length of the returned path), and it was subsequently improved to 0 (1) [29, 11]. A major drawback of the oracle of [27] is that its space is ω (n.·log vi). Mendel and Naor [18] devised an oracle with space O (n^1+1/k) and stretch O (k), but their oracle can only report distance estimates and not actual paths. In this paper we devise a path-reporting distance oracle with size O (n^1+1/k), stretch O (k) and query time O (nε), for an arbitrarily small ε > 0. In particular, for k=logn our oracle provides logarithmic stretch using linear size. Another variant of our oracle has linear size, polylogarithmic stretch, and query time O (1og log vi). For unweighted graphs we devise a distance oracle with multiplicative stretch O (1), additive stretch O (β (k)), for a function β, space O (n^1+1/kk · β), and query time O (n), for an arbitrarily small constant ε> o T he tradeoff between multiplicative stretch and size in these oracles is far below Erdôs's girth conjecture threshold (which is stretch 2k-1 and size O (n^1+1/kk)).