Approximate distance oracles
Top Cited Papers
- 1 January 2005
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 52 (1), 1-24
- https://doi.org/10.1145/1044731.1044732
Abstract
Let G = (V,E) be an undirected weighted graph with |V| = n and |E| = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn1/k) expected time, constructing a data structure of size O(kn1+1/k), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k−1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k−1. A 1963 girth conjecture of Erdós, implies that Ω(n1+1/k) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O(n1+1/k) space had a query time of Ω(n1/k).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.Keywords
This publication has 42 references indexed in Scilit:
- External memory algorithms and data structuresACM Computing Surveys, 2001
- Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential AlgorithmsAlgorithmica, 2000
- A Reliable Randomized Algorithm for the Closest-Pair ProblemJournal of Algorithms, 1997
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functionsAlgorithmica, 1996
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- All-pairs shortest paths and the essential subgraphAlgorithmica, 1995
- New Examples of Graphs without Small Cycles and of Large SizeEuropean Journal of Combinatorics, 1993
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Über ein Problem von K. ZarankiewiczActa Mathematica Hungarica, 1958