 |
|
(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 data-structure 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 data-structure is that, for $t>2$,
it occupies sub-quadratic space, i.e., it does not store all-pairs distances information explicitly, and still can answer
any $t$-approximate distance query in constant time. They named the data-structure "oracle" because of this feature. Furthermore, the tradeoff between stretch $t$ and the size of the data-structure 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 |
|