Incremental Single Source Shortest Paths in Sparse Digraphs
Incremental Single Source Shortest Paths in Sparse Digraphs
复制标题
稀疏有向图中增量单源最短路径
DOI：
10.1137/1.9781611976465.146
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tianyi Zhang
中科院分区：
文献类型：
--
作者：
S. Chechik;Tianyi Zhang
给定一个具有正整数边权重的有向图G =（V，E，ω），它经历了一系列的边插入，我们感兴趣的是在增量图G中保持近似的单源最短路径。在最近的一篇论文中，[Gutenberget al.，2020]提出了一个确定性算法来解决这个问题，总更新时间为n（n2 logW），其中n =| V| W表示最大边权重。当底层图是超稠密的，即插入的总数是时，它们的上界本质上是最优的。对于稀疏图，唯一已知的结果是由于[Henzingeret al.，2014]，其算法是随机的，在不经意非自适应攻击者的假设下，其总更新时间不超过（mn0.9logW）。第一个是一个简单的确定性算法，总更新时间为n（m5/3logW）。第二个是一个总更新时间为n（（mn 1/2+m7/5）logW）的随机化算法，改进了m =O（n1.42）时的两个结果，并且该随机化算法可以对抗自适应对手。我们的算法是第一个打破theO（mn）约束与自适应对手稀疏图。
Given a directed graphG= (V, E, ω) with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graphG. In a very recent paper, [Gutenberget al., 2020] proposed a deterministic algorithm for this problem withÕ(n2logW) total update time, wheren=|V|andWdenotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertionsmis , their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzingeret al., 2014], whose algorithm is randomized and works inÕ(mn0.9logW) total update time under the assumption of oblivious non-adaptive adversary.In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm withÕ(m5/3logW) total update time. The second one is a randomized algorithm withÕ((mn1/2+m7/5) logW) total update time, which improves over both previous results whenm=O(n1.42); moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break theO(mn) bound with adaptive adversaries for sparse graphs.