论文标题
加权挖掘中的SSSP减少：更快，自适应对手
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
论文作者
论文摘要
给定一个动态挖掘$ g =（v，e）$正在进行边缘删除，并给定$ s \ in V $和$ε> 0 $，我们考虑了维持$（1+ε）$的问题 - 大约最短的路径距离，从$ s $到所有$ g $ in $ g $ the $ g $ the $ g $ after of detece fac of detece of detece sefence by the detece sefence by the the detece。偶数和Shiloach（J.〜ACM'$ 81 $）为问题的确切版本提供了确定性的数据结构，其中总更新时间$ O（MN）$。 Henzinger等。 （Stoc' $ 14 $，ICALP' $ 15 $）给出了大约版本的蒙特卡洛数据结构，并改善了总更新时间$ o（mn^{0.9 + o（1）} \ log w）$，其中$ w $是最大和最小的边缘重量之间的比例。他们的数据结构的缺点是它们仅针对遗忘的对手，这意味着需要预先确定删除的顺序。这限制了其在算法内部的黑匣子的应用。我们提供以下$（1+ε）$ - 近似数据结构： （1）第一个数据结构是拉斯维加斯，对抗自适应对手；它的总预期更新时间$ \ tilde o（m^{2/3} n^{4/3}）$用于未加权图，$ \ tilde o（m^{3/4} n^{5/4} {5/4} \ log w）$用于加权图， （2）第二个数据结构是拉斯维加斯，并假定遗忘的对手；它的总预期更新时间$ \ tilde o（\ sqrt m n^{3/2}）$用于未加权图和$ \ tilde o（m^{2/3} n^{4/3} {4/3} \ log w）$ for加权图， （3）第三个数据结构是蒙特卡洛，是正确的w.h.p.〜对遗忘的对手；它具有总预期的更新时间$ \ tilde o（（（mn）^{7/8} \ log W）= \ tilde o（mn^{3/4} \ log w）$。 我们的每个数据结构都可以在$ g $的任何阶段都在恒定最差的时间内查询；如果对手遗忘，则可以扩展查询以报告与时间成正比的时间。对于所有图形密度，我们的更新时间比Henzinger等人的更新时间快。
Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $s\in V$ and $ε>0$, we consider the problem of maintaining $(1+ε)$-approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions. Even and Shiloach (J.~ACM'$81$) give a deterministic data structure for the exact version of the problem with total update time $O(mn)$. Henzinger et al. (STOC'$14$, ICALP'$15$) give a Monte Carlo data structure for the approximate version with improved total update time $ O(mn^{0.9 + o(1)}\log W)$ where $W$ is the ratio between the largest and smallest edge weight. A drawback of their data structure is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This limits its application as a black box inside algorithms. We present the following $(1+ε)$-approximate data structures: (1) the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time $\tilde O(m^{2/3}n^{4/3})$ for unweighted graphs and $\tilde O(m^{3/4}n^{5/4}\log W)$ for weighted graphs, (2) the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time $\tilde O(\sqrt m n^{3/2})$ for unweighted graphs and $\tilde O(m^{2/3}n^{4/3}\log W)$ for weighted graphs, (3) the third data structure is Monte Carlo and is correct w.h.p.~against an oblivious adversary; it has total expected update time $\tilde O((mn)^{7/8}\log W) = \tilde O(mn^{3/4}\log W)$. Each of our data structures can be queried at any stage of $G$ in constant worst-case time; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al.~for all graph densities.
