Baswana, Surender ; Sen, Sandeep
(2006)
*Approximate distance oracles for unweighted graphs in expected O(n ^{2}) time*
ACM Transactions on Algorithms, 2
(4).
No pp. given.
ISSN 1549-6325

Full text not available from this repository.

Official URL: http://portal.acm.org/citation.cfm?id=1198518

Related URL: http://dx.doi.org/10.1145/1198513.1198518

## Abstract

Let G = (V, E) be an undirected graph on n vertices, and let δ(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∈V, the distance reported is
at least d(u, v) and at most tδ(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, such
that for any two vertices u and v in the graph, their distance in the subgraph is at most 2δ(u, v) + 1.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Association for Computing Machinery. |

ID Code: | 53441 |

Deposited On: | 08 Aug 2011 12:13 |

Last Modified: | 08 Aug 2011 12:13 |

Repository Staff Only: item control page