Approximate Distance Oracles with Improved Query Time
Christian Wulff‐Nilsen · 2013
Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 2, we show that a (2k − 1)-approximate distance oracle for G of size O(kn1+1/k) and with O(log k) query time can be constructed in O(min{kmn1/k, √km + kn1+c/ √k}) time for some constant c. This improves the O(k) query time of Thorup and Zwick. Furthermore, for any 0 0 and k = O (log n/ log log n).