论文标题
完全动态的全对最短路径：改善最差的时间和空间边界
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
论文作者
论文摘要
给定有针对的加权图$ g =（v，e）$正在进行顶点插入\ emph {and}删除，全对最短路径（APSP）问题要求维护一个数据结构，以有效地进行处理并在每次更新为$ g $的当前版本后返回后返回。在两个突破结果中，Italiano和demetrescu [Stoc '03]提出了一种算法，需要$ \ tilde {o}（n^2）$ \ emph {amortized}更新时间，而Thorup在[stoc '05]中显示了\ emph {wort-case} wort-case} time $ $ \ tilde $ \ tilde $ \ tilde $ \ tilde {o \ tilde} {可以实现。在本文中，我们在问题上取得了长足的进步。我们提出以下新结果： （1）我们提出了第一个确定性数据结构，它打破了$ \ tilde {o}（n^{2+3/4}）$糟糕的更新时间由Thorup绑定的时间已有将近15年。我们将最差的更新时间提高到$ \ tilde {o}（n^{2+5/7}）= \ tilde {o}（n^{2.71 ..}）$和$ \ tilde {o}}（n^{2+3/5}） （2）我们提出了一种简单的确定性算法，并带有$ \ tilde {o}（n^{2+3/4}）$最差的更新时间（$ \ tilde {o}（n^{2+2/3}）$用于未量的图形），以及简单的Las-vegaS Algorithm $ \ tilde {o}（n^{2 + 2/3}）$（$ \ tilde {o}（n^{2 {2 + 1/2}）$用于未加权的图形），以对抗非卑鄙的对手。两个数据结构都需要空间$ \ tilde {o}（n^2）$。这些是第一个具有真正掩体更新时间\ emph {and}空间用法的精确动态算法。这在多个文章中提出的一个开放问题上取得了重大进展[Cocoon'01，STOC '03，ICALP'04，算法百科全书'08]，并且在实践中对算法[TALG '06]中的算法至关重要。此外，它们与以前最佳算法的最差更新时间相匹配，第二算法在具有相同运行时间的较弱的对手模型中，在蒙特卡罗算法上有所改善[苏打水'17]。
Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions \emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of $G$. In two breakthrough results, Italiano and Demetrescu [STOC '03] presented an algorithm that requires $\tilde{O}(n^2)$ \emph{amortized} update time, and Thorup showed in [STOC '05] that \emph{worst-case} update time $\tilde{O}(n^{2+3/4})$ can be achieved. In this article, we make substantial progress on the problem. We present the following new results: (1) We present the first deterministic data structure that breaks the $\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to $\tilde{O}(n^{2+5/7}) = \tilde{O}(n^{2.71..})$ and to $\tilde{O}(n^{2+3/5}) = \tilde{O}(n^{2.6})$ for unweighted graphs. (2) We present a simple deterministic algorithm with $\tilde{O}(n^{2+3/4})$ worst-case update time ($\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time $\tilde{O}(n^{2+2/3})$ ($\tilde{O}(n^{2 + 1/2})$ for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space $\tilde{O}(n^2)$. These are the first exact dynamic algorithms with truly-subcubic update time \emph{and} space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP'04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].
