Approximate Distance Oracles with Improved Bounds
Approximate Distance Oracles with Improved Bounds
复制标题
具有改进边界的近似距离预言机
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Chechik
中科院分区：
文献类型：
--
作者：
S. Chechik
距离oracle是一种紧凑的数据结构，能够快速估计给定图中的距离。本文给出了一般无向加权图中距离预言的一种新构造。对于任意整数k，我们的数据结构需要O（n1+1/k）空间，保证2k-1的延伸，并且在O(1)时间内回答任何查询。
A distance oracle is a compact data structure capable of quickly estimating distances in a given graph. In this paper we provide a new construction for distance oracles in general undirected weighted graphs. Our data structure, for any integer k, requires O( n1+1/k) space, guarantees a stretch of 2k-1, and answers any query in only O(1) time.