Approximate Distance Oracles with Improved Preprocessing Time

Abstract

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\ge 1$, we show that for some universal constant $c$, a $(2k-1)$-approximate distance oracle for $G$ of size $O(k{n}^{1+1/k})$ can be constructed in $O(\sqrt{k}m+k{n}^{1+c/\sqrt{k}})$ time and can answer queries in $O(k)$ time. We also give an oracle which is faster for smaller $k$. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all $k\ge 6$ and improve the $O(km{n}^{1/k})$ time bound of Thorup and Zwick except for very sparse graphs and small $k$. When $m=\Omega (n^{1+c/\sqrt{k}})$ and $k=O(1)$, our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erdős.

To appear at the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, 2012