Approximate Distance Oracles for Unweighted Graphs in Expected O(n(2)) Time
Let G = (V, E) be an undirected graph on n vertices, and let delta(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive integer t, the graph G can be preprocessed to build a data structure that can efficiently report t-approximate distance between any pair of vertices. That is, for any u, v is an element of V, the distance reported is at least delta(u, v) and at most t delta(u, v). The remarkable feature of this data structure is that, for t >= 3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t-approximate distance query in constant time. They named the data structure "approximate distance oracle" because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal. In this article, we show that we can actually construct approximate distance oracles in expected O(n(2)) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G = (V, E) is a subgraph (V, (E) over cap), (E) over cap subset of E, such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2 delta(u, v) + 1.
approximate distance oracles distances distance queries algorithms spanners theory shortest paths