Deterministic decremental single source shortest paths: beyond the o(mn) bound
Deterministic decremental single source shortest paths: beyond the o(mn) bound
复制标题
确定性递减单源最短路径：超出 o(mn) 界限
DOI：
10.1145/2897518.2897521
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Chechik
中科院分区：
文献类型：
--
作者：
A. Bernstein;S. Chechik
在本文中，我们考虑减少单源最短路径（SSSP）问题，其中给定图G和A源节点S的目标是在一系列在线对抗边缘删除序列中保持S和所有其他节点之间的最短路径。减少SSSP问题，即使允许近似最短的路径。 +）具有恒定查询时间的算法和O（N2+O（1/√logn）的总更新时间）。 Henzinger，Krinninger和Nanongkai [Focs 14]提出了一种算法，其总更新时间接近线性O（M1+ O（1/√logn））。结果。可以从对手中“隐藏”这些节点，在确定性的环境中，这是不可能的：对手可以删除所有接触这些节点的边缘，从而迫使算法选择一组新的节点并触发最短路径的新计算。在本文中，我们介绍了第一个确定性的SSSP算法，它破坏了O（MN）总更新时间的均匀和无方向性的算法。大约实现了我们的算法的总更新时间（N2）。我们的算法也比所有现有的随机算法快。
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+) algorithm with constant query time and a total update time of O(n2+O(1/√logn)). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a -approximate algorithm whose total update time is near linear O(m1+ O(1/√logn)). In this paper they posed as a major open problem the question of derandomizing their result. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths. In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs. Our algorithm is (1 + є) approximate and achieves a total update time of Õ(n2). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω(n2 − 1/√log(n)), our algorithm is also faster than all existing randomized algorithms.