期刊
JOURNAL OF THE ACM
卷 52, 期 1, 页码 1-24出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1044731.1044732
关键词
algorithms; theory; approximate distance oracles; spanners; distance labelings; shortest paths; distance queries; distances
Let G = (V, E) be an undirected weighted graph with \V\ = n and I E I = m. Let k greater than or equal to 1 be an integer. We show that G = (V, E) can be preprocessed in O(kmn(1/k)) expected time, constructing a data structure of size O(kn(1+1/k)), such that any subsequent distance query can be answered, approximately, in 0(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 Erdos, implies that Omega(n(1+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(n(1+1/k)) space had a query time of Omega(n(1/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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据