Faster Replacement Paths and Distance Sensitivity Oracles
Faster Replacement Paths and Distance Sensitivity Oracles
复制标题
更快的替换路径和距离敏感性预言机
DOI：
10.1145/3365835
复制
发表时间：
2019
影响因子：
1.3
通讯作者：
Williams, Virginia Vassilevska
中科院分区：
文献类型：
--
作者：
Grandoni, Fabrizio;Williams, Virginia Vassilevska
最短路径计算是计算机科学中最基本的问题之一。该问题的一个重要变体是当边缘可能失败时，需要计算避免（失败）边缘的最短路径。更正式地，给定源节点、目标节点和边缘，三元组 (s,t,e) 的替换路径是避免边缘的最短 t 路径。替换路径计算可以被视为静态问题或数据结构问题。在静态设置中，典型的目标是计算固定沙，对于每个可能失败的边缘，周围最佳替换路径的长度（替换路径问题）。在数据结构设置中，一个典型的目标是设计一个数据结构（距离敏感性预言机），经过一些预处理后，快速回答以下形式的查询：三元组（s，t，e）的替换路径的长度是多少？在本文中，我们关注具有整数边权重为[−M，M]的n节点有向图，并提出基于快速矩阵乘法的改进的替换路径算法和距离敏感性预言机。更详细地说，我们获得了以下主要结果： • 我们描述了一种运行时间为Õ(Mnω) 的替换路径算法，其中ω < 2.373 是快速矩阵乘法指数。为了进行比较，以前最快的算法的运行时间为 õ(Mn1+2ω /3) [Weimann,Yuster-FOCS'10]，在未加权的情况下，运行时间为 õ(n2.5) [Roditty, Zwick-ICALP'05]。我们的结果表明，至少对于小整数权重，有向图中的替换路径问题可能比相关的全对最短路径问题更容易，因为后者的当前最佳运行时间是 õ(M1\4−ωn2+1 \ 4−ω)：即使 ω = 2，这也是 Ω (n2.5)。我们的算法还意味着可以在 õ(kMnω) 时间内计算最短的简单 t 路径。• 我们考虑替换路径问题的单源概括，其中仅固定源。我们展示了如何在所有对最短路径时间内解决这个问题，目前为 õ(M1\4−ωn2+1\4−ω)。对于正权重，我们的运行时间减少到 õ(Mnω)，因此与我们提到的更简单的替换路径情况的结果相匹配（然而，这也适用于非正权重）。我们使用的成分之一是一种算法，用于在 õ(Mnω+|S|ṡ |T|ṡ (Mn)1\4−ω) 时间内计算从一组源节点到一组Tof 目标节点的距离。这改进了 Yuster,Zwick — FOCS’05 中的结果。• 我们提出了第一个距离灵敏度预言机，它同时实现了亚立方预处理时间和亚线性查询时间。更准确地说，对于给定参数 α ∈ [0,1]，我们的预言机具有预处理时间 Õ(Mnω + 1\ 2+Mnω + α (4−ω)) 和查询时间 Õ(n1−&alpha)。之前针对小整数权重的最佳预言机具有 Õ(Mnω +1−α) 预处理时间和（超线性）Õ(n1+α) 查询时间 [Weimann,Yuster-FOCS’10]。从技术角度来看，我们的预言机的一个有趣且新颖的方面是，它利用我们的单源替换路径算法作为子例程。我们还提出了一个预言机，其预处理时间与 Weimann,Yuster—FOCS’10 相同，但查询时间更短 õ(n1−1−α\4−ω+n2α)。
Shortest paths computation is one of the most fundamental problems in computer science. An important variant of the problem is when edges can fail, and one needs to compute shortest paths that avoid a (failing) edge. More formally, given a source nodes, a target nodet, and an edgee, areplacement pathfor the triple (s,t,e) is a shortests-tpath avoiding edgee. Replacement paths computation can be seen either as a static problem or as a data structure problem. In the static setting, a typical goal is to compute for fixedsandt, for every possible failed edgee, the length of the best replacement path arounde(replacement paths problem). In the data structure setting, a typical goal is to design a data structure (distance sensitivity oracle) that, after some preprocessing,quicklyanswers queries of the form: What is the length of the replacement path for the triple (s,t,e)?In this article, we focus onn-node directed graphs with integer edge weights in [−M,M], and present improved replacement paths algorithms and distance sensitivity oracles based on fast matrix multiplication. In more detail, we obtain the following main results:• We describe a replacement paths algorithm with runtime Õ(Mnω), where ω < 2.373 is the fast matrix multiplication exponent. For a comparison, the previous fastest algorithms have runtime õ(Mn1+2ω /3) [Weimann,Yuster—FOCS’10] and, in the unweighted case, õ(n2.5) [Roditty, Zwick—ICALP’05]. Our result shows that, at least for small integer weights, the replacement paths problem in directed graphs may be easier than the related all-pairs shortest paths problem, as the current best runtime for the latter is õ(M1\4−ωn2+1 \ 4−ω): this is Ω (n2.5) even if ω = 2. Our algorithm also implies that thekshortest simples-tpaths can be computed in õ(kMnω) time.• We consider thesingle-sourcegeneralization of the replacement paths problem, where only the sourcesis fixed. We show how to solve this problem in all-pairs shortest paths time, currently õ(M1\4−ωn2+1\4−ω). Our runtime reduces to õ(Mnω) for positive weights, hence matching our mentioned result for the simpler replacement paths case (that, however, holds also for nonpositive weights). One of the ingredients that we use is an algorithm to compute the distances from a setsof source nodes to a setTof target nodes in õ(Mnω+|S|ṡ |T|ṡ (Mn)1\4−ω) time. This improves on a result in Yuster,Zwick—FOCS’05.• We present the first distance sensitivity oracle that achieves simultaneously subcubic preprocessing time and sublinear query time. More precisely, for a given parameter α ∈ [0,1], our oracle has preprocessing time Õ(Mnω + 1\ 2+Mnω + α (4−ω)) and query time Õ(n1−&alpha). The previous best oracle for small integer weights has Õ(Mnω +1−α) preprocessing time and (superlinear) Õ(n1+α) query time [Weimann,Yuster-FOCS’10]. From a technical point of view, an interesting and novel aspect of our oracle is that it exploits as a subroutine our single-source replacement paths algorithm. We also present an oracle with the same preprocessing time as in Weimann,Yuster—FOCS’10 and with smaller query time õ(n1−1−α\4−ω+n2α).
登录
查看更多内容
最佳顶点容错扳手（用于固定拉伸）
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Gregory Bodwin;M. Dinitz;M. Parter;V. V. Williams
通讯作者：
V. V. Williams
一种用于计算平面有向图中替换路径的近线性时间算法
DOI：
--
发表时间：
2008
期刊：
TALG
影响因子：
--
作者：
Y. Emek;D. Peleg;L. Roditty
通讯作者：
L. Roditty
DOI：
--
发表时间：
2009
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Ran Duan;Seth Pettie
通讯作者：
Seth Pettie
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Amit M. Bhosle
通讯作者：
Amit M. Bhosle
更快的更换路径
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
V. V. Williams
通讯作者：
V. V. Williams