Parallel Shortest Paths with Negative Edge Weights
Parallel Shortest Paths with Negative Edge Weights
复制标题
具有负边权重的并行最短路径
DOI：
10.1145/3490148.3538583
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Russell, Katina
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
本文针对边权为整数（包括负）的单源最短路径问题，提出了一种并行版本的Goldberg算法。给定一个n个顶点，m条边，整数权值≥-N的输入图，我们的算法以Õ（m√n log n）的工作量和n5/4+o(1) log n的空间解决问题，两者都具有高概率。因此，我们的算法在实现至少m1/4- 0(1)并行性的同时，其工作原理与Goldberg的算法相似。为了生成我们的并行版本的Goldberg算法，我们解决了两个特定的距离限制的最短路径问题，这两个问题都有功Õ(m)和跨度√L·n1/2+o(1)，其中L是距离限制。
This paper presents a parallel version of Goldberg's algorithm for the problem of single-source shortest paths with integer (including negatives) edge weights. Given an input graph with n vertices, m edges, and integer weights ≥-N, our algorithms solves the problem with Õ(m √n log N) work and n5/4+o(1) log N span, both with high probability. Our algorithm thus has work similar to Goldberg's algorithm while also achieving at least m1/4-o(1) parallelism. To generate our parallel version of Goldberg's algorithm, we solve two specific distance-limited shortest-path problems, both with work Õ(m) and span √L · n1/2+o(1), where L is the distance limit.
登录
查看更多内容
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
只需加入并行有序集
DOI：
10.1145/2935764.2935768
发表时间：
2016
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Daniel Ferizovic;Yihan Sun
通讯作者：
Yihan Sun
DOI：
10.1006/jagm.1997.0888
发表时间：
1997
期刊：
J. Algorithms
影响因子：
--
作者：
P. Klein;Sairam Subramanian
通讯作者：
Sairam Subramanian
近似最短路径的更快并行算法
DOI：
--
发表时间：
2019
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Jason Li
通讯作者：
Jason Li
中等密集图上近线性时间的二分匹配
DOI：
10.1109/focs46700.2020.00090
发表时间：
2020
期刊：
2020
影响因子：
--
作者：
van den Brand, Jan;Lee, Yin-Tat;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
通讯作者：
Wang, Di