Distance oracles with near-linear preprocessing time for undirected graphs

Christian Wulff-Nilsen

Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given a positive integer k, I will show that for some constant c, a (2k - 1)-approximate distance oracle for G of size O(kn^{1 + 1/k}) can be constructed in O(m + kn^{1 + c/sqrt k}) time and can answer queries in O(k) time. This breaks the quadratic preprocessing time bound of Baswana and Kavitha for all k greater than 5 and improves the O(kmn^{1/k}) time bound of Thorup and Zwick except for very sparse graphs and very small k. When m = Omega(n^{1 + c/sqrt k}), our algorithm is essentially optimal w.r.t. both stretch, size, preprocessing time, and query time, assuming a widely believed and partially proved girth conjecture by Erdos from 1963.