Deterministic Constructions of Approximate Distance Oracles and Spanners
Deterministic Constructions of Approximate Distance Oracles and Spanners
复制标题
近似距离预言机和扳手的确定性构造
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Uri Zwick
中科院分区：
文献类型：
--
作者：
L. Roditty;M. Thorup;Uri Zwick
索鲁普（Thorup）和兹维克（Zwick）表明，对于任何整数\(k\geq1\)，都可以对任何具有\(|E| = m\)和\(|V| = n\)的正权无向图\(G=(V,E)\)在\(O(kmn^{\frac{1}{k}})\)的期望时间内进行预处理，并构建一个大小为\(O(kn^{1 + \frac{1}{k}})\)的数据结构（一个\((2k - 1)\) - 近似距离预言机），该数据结构能够在\(O(k)\)时间内返回图\(G\)中从\(u\)到\(v\)的距离\(\delta(u,v)\)的一个近似值\(\hat{\delta}(u,v)\)，对于任何两个顶点\(u,v\in V\)，满足\(\delta(u,v)\leq\hat{\delta}(u,v)\leq(2k - 1)\cdot\delta(u,v)\)。他们还提出了一种慢得多的\(O(kmn)\)时间的确定性算法，用于构建大小略大（为\(O(kn^{1 + \frac{1}{k}}\log n)\)）的近似距离预言机。我们在此提出一种确定性的\(O(kmn^{\frac{1}{k}})\)时间算法，用于构建大小为\(O(kn^{1 + \frac{1}{k}})\)的预言机。我们的确定性算法仅比随机算法慢一个对数因子。
利用我们的去随机化技术，我们还获得了第一个用于构建加权图的最优生成树的确定性线性时间算法。我们通过对巴斯瓦纳（Baswana）和森（Sen）（ICALP’03）的\(O(km)\)期望时间算法进行去随机化来实现这一点，该算法用于构建加权无向图的大小为\(O(kn^{1 + \frac{1}{k}})\)的\((2k - 1)\) - 生成树，且在运行时间或所生成的生成树的大小上没有任何渐近损失。
Thorup and Zwick showed that for any integer k≥ 1, it is possible to preprocess any positively weighted undirected graph G=(V,E), with |E|=m and |V|=n, in O(kmn$^{\rm 1/{\it k}}$) expected time and construct a data structure (a (2k–1)-approximate distance oracle) of size O(kn$^{\rm 1+1/{\it k}}$) capable of returning in O(k) time an approximation $\hat{\delta}(u,v)$ of the distance δ(u,v) from u to v in G that satisfies $\delta(u,v) \leq \hat{\delta}(u,v) \leq (2k -1)\cdot \delta(u,v)$, for any two vertices u,v∈ V. They also presented a much slower O(kmn) time deterministic algorithm for constructing approximate distance oracle with the slightly larger size of O(kn$^{\rm 1+1/{\it k}}$log n). We present here a deterministic O(kmn$^{\rm 1/{\it k}}$) time algorithm for constructing oracles of size O(kn$^{\rm 1+1/{\it k}}$). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor.
Using our derandomization technique we also obtain the first deterministic linear time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the O(km) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2k–1)-spanners of size O(kn$^{\rm 1+1/{\it k}}$) of weighted undirected graphs without incurring any asymptotic loss in the running time or in the size of the spanners produced.