

(LaTeX) Abstract: 
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 +ve integer $t$, the
graph $G$ can be preprocessed to build a datastructure that can efficiently report $t$approximate distance between any pair of vertices. That is, for any $u,v\in V$, the distance reported $\hat{\delta}(u,v)$ satisfies
\[
\delta(u,v) \le \hat{\delta}(u,v) \le t \delta(u,v)
\]
The remarkable feature of this datastructure is that, for $t>2$,
it occupies subquadratic space, i.e., it does not store allpairs distances information explicitly, and still can answer
any $t$approximate distance query in constant time. They named the datastructure "oracle" because of this feature. Furthermore, the tradeoff between stretch $t$ and the size of the datastructure is essentially optimal.
In this paper 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 a graph $G=(V,E)$ is a subgraph $G=(V,E_S), E_S\subset 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$. 
Keywords: 
Distance, Shortest Path, Graph Algorithm 


Personal Comments: 
The paper is a revised version of the paper that appeared in the conference SODA 2004. 
Download
Access Level: 
Public 
