Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
复制标题
通过快速矩阵乘法替换路径和距离敏感度预言
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
Oren Weimann;R. Yuster
一个<i>n</i>顶点图<i>G</i>=（<i>V</i>，<i>E</i>）的<i>距离敏感预言机</i>是一种当图的边失效时可以报告最短路径的数据结构。对这个预言机的查询（<i>u</i>∈<i>V</i>，<i>v</i>∈<i>V</i>，<i>S</i><$<i>E</i>）返回图<i>G</i><sup>′</sup>=（<i>V</i>，<i>E</i><$<i>S</i>）中的最短<i>u</i>到<i>v</i>路径。我们提出了随机（蒙特卡罗）算法，用于构建大小为<i>n</i>（<i>n</i><sup>3−α</sup>）的距离敏感性预言，|<i>S</i>| = <i>O</i>（lg <i>n</i>/lg lg <i>n</i>）且任意选择0 <<i>α</i> < 1。对于真实的边长度，预言机的构造时间为<i>O</i>（<i>n</i><sup>4−α</sup>），对这个预言机的查询时间为<i>n</i>（<i>n</i><sup>2−2（1−α）/|S|</sup>）时间。对于{−<i>M</i>，.，<i>M</i>}，使用当前<i>ω</i> < 2.376的矩阵乘法指数，在<i>O</i>（<i>Mn</i><sup>3.376−α</sup>）时间内构造预言机，其中<i><$</i>（<i>n</i><sup>2−（1−α）/|S|</sup>时间复杂度为<i>O</i>（<i>M</i><sup>0.681</sup><i>n</i><sup>3.575−α</sup>），时间复杂度为<i>O</i>（<i>n</i><sup>2−2（1−α））。|S|</sup>）查询。
距离敏感预言机推广了<i>替换路径</i>问题，其中<i>u</i>和<i>v</i>是预先已知的，|<i>S</i>| = 1。换句话说，如果<i>P</i>是<i>G</i>中从<i>u</i>到<i>v</i>的最短路径，则替换路径问题要求为<i>P</i>上的每条边<i>e</i>计算避免<i>e</i>的最短<i>u</i>到<i>v</i>路径。我们的新技术，使用快速矩阵乘法构建距离敏感性预言也产生了第一个子时间算法的替换路径问题时，边长是小整数。特别地，在<i>M</i>≤<i>n0.624的</i><sup>条件下，</sup>给出了一个求解替换路径问题的随机（MonteCarlo）<i>n</i>（<sup>Mn2.376</sup>+<sup>M23n2.584</sup>）时间算法.<i></i><sup></sup><i></i><i></i>
最后，我们提到，我们的替换路径算法和我们的距离灵敏度预言机可以工作，在相同的时间和空间范围内，对于失败的顶点而不是边缘的情况，也就是说，当<i>S</i>是一组顶点，我们寻求最短的<i>u</i>到<i>v</i>路径从<i>G</i>获得的图中删除所有顶点在<i>S</i>和它们的相邻边缘。
A <i>distance sensitivity oracle</i> of an <i>n</i>-vertex graph <i>G</i> = (<i>V</i>,<i>E</i>) is a data structure that can report shortest paths when edges of the graph fail. A query (<i>u</i> ∈ <i>V</i>, <i>v</i> ∈ <i>V</i>, <i>S</i> ⊆ <i>E</i>) to this oracle returns a shortest <i>u</i>-to-<i>v</i> path in the graph <i>G</i><sup>′</sup> = (<i>V</i>,<i>E</i> ∖ <i>S</i>). We present randomized (Monte Carlo) algorithms for constructing a distance sensitivity oracle of size <i>Õ</i>(<i>n</i><sup>3−α</sup>) for |<i>S</i>| = <i>O</i>(lg <i>n</i>/lg lg <i>n</i>) and any choice of 0 < <i>α</i> < 1. For real edge-lengths, the oracle is constructed in <i>O</i>(<i>n</i><sup>4−α</sup>) time and a query to this oracle takes <i>Õ</i>(<i>n</i><sup>2−2(1−α)/|S|</sup>) time. For integral edge-lengths in {−<i>M</i>,..., <i>M</i>}, using the current <i>ω</i> < 2.376 matrix multiplication exponent, the oracle is constructed in <i>O</i>(<i>Mn</i><sup>3.376−α</sup>) time with <i>Õ</i>(<i>n</i><sup>2−(1−α)/|S|</sup>) query, or alternatively in <i>O</i>(<i>M</i><sup>0.681</sup><i>n</i><sup>3.575−α</sup>) time with <i>Õ</i>(<i>n</i><sup>2−2(1−α)/|S|</sup>) query.
Distance sensitivity oracles generalize the <i>replacement paths</i> problem in which <i>u</i> and <i>v</i> are known in advance and |<i>S</i>| = 1. In other words, if <i>P</i> is a shortest path from <i>u</i> to <i>v</i> in <i>G</i>, then the replacement paths problem asks to compute, for every edge <i>e</i> on <i>P</i>, a shortest <i>u</i>-to-<i>v</i> path that avoids <i>e</i>. Our new technique for constructing distance sensitivity oracles using fast matrix multiplication also yields the first subcubic-time algorithm for the replacement paths problem when the edge-lengths are small integers. In particular, it yields a randomized (Monte Carlo) <i>Õ</i>(<i>Mn</i><sup>2.376</sup> + <i>M</i><sup>2 3</sup> <i>n</i><sup>2.584</sup>)-time algorithm for the replacement paths problem assuming <i>M</i> ≤ <i>n</i><sup>0.624</sup>.
Finally, we mention that both our replacement paths algorithm and our distance sensitivity oracle can be made to work, in the same time and space bounds, for the case of failed vertices rather than edges, that is, when <i>S</i> is a set of vertices and we seek a shortest <i>u</i>-to-<i>v</i> path in the graph obtained from <i>G</i> by removing all vertices in <i>S</i> and their adjacent edges.