Approximate distance oracles for unweighted graphs in expected O(n2) time

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

Full text not available from this repository.

Official URL:

Related URL:


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(n2) 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