Distance sensitivity oracles with subcubic preprocessing time and fast query time
Distance sensitivity oracles with subcubic preprocessing time and fast query time
复制标题
具有亚立方预处理时间和快速查询时间的距离敏感性预言机
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Cohen
中科院分区：
文献类型：
--
作者：
S. Chechik;S. Cohen
对于权值在[−M，M]范围内的整数有向图，我们提出了第一个具有亚立方预处理时间和多对数查询时间的距离灵敏度oracle （DSO）。Weimann和Yuster [FOCS 10]提出了一种单顶点/边故障的距离灵敏度预测方法，其亚三次预处理时间为O(Mn ω+1−α)，次二次查询时间为Õ（n 1+α），其中α为[0,1]中的任意参数，n为顶点数，m为边数，Õ（·）符号隐藏了n中的多对数因子，ω<2.373为矩阵乘法指数。后来，Grandoni和Vassilevska Williams [FOCS 12]将查询时间大幅提高到n的亚线性。特别是，他们提出了一个单顶点/边故障的距离灵敏度预测，其预处理时间为Õ（Mn ω+1/2+ Mn ω+α(4−ω)），查询时间为Õ（n 1−α）。尽管在查询时间上有了很大的改进，但它在图的大小上仍然是多项式的，这在许多图的大规模设置中可能是不可取的。一个自然的问题是，人们是否可以期望一个距离敏感的oracle具有亚立方预处理时间和非常快的查询时间（n的多对数）。本文给出了一个支持单顶点/边故障的距离敏感oracle，其预处理时间为ω=2.373 Õ（Mn 2.873），预处理时间为Õ（n 2.5），查询时间为Õ(1)。相比之下，在相同的Õ（Mn 2.873）预处理时间下，Grandoni和Vassilevska Williams的DSO查询时间为Õ（n 0.693）。实际上，他们的算法可以获得的最佳查询时间是（Mn 0.385）（预处理时间为（Mn 3））。
We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range [−M,M]. Weimann and Yuster [FOCS 10] presented a distance sensitivity oracle for a single vertex/edge failure with subcubic preprocessing time of O(Mn ω+1−α) and subquadratic query time of Õ(n 1+α), where α is any parameter in [0,1], n is the number of vertices, m is the number of edges, the Õ(·) notation hides poly-logarithmic factors in n and ω<2.373 is the matrix multiplication exponent. Later, Grandoni and Vassilevska Williams [FOCS 12] substantially improved the query time to sublinear in n. In particular, they presented a distance sensitivity oracle for a single vertex/edge failure with Õ(Mn ω+1/2+ Mn ω+α(4−ω)) preprocessing time and Õ(n 1−α) query time. Despite the substantial improvement in the query time, it still remains polynomial in the size of the graph, which may be undesirable in many settings where the graph is of large scale. A natural question is whether one can hope for a distance sensitivity oracle with subcubic preprocessing time and very fast query time (of poly-logarithmic in n). In this paper we answer this question affirmatively by presenting a distance sensitive oracle supporting a single vertex/edge failure in subcubic Õ(Mn 2.873) preprocessing time for ω=2.373, Õ(n 2.5) space and near optimal query time of Õ(1). For comparison, with the same Õ(Mn 2.873) preprocessing time the DSO of Grandoni and Vassilevska Williams has Õ(n 0.693) query time. In fact, the best query time their algorithm can obtain is (Mn 0.385) (with (Mn 3) preprocessing time).