Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm
Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm
复制标题
简短公告：改进的分布式近似单源最短路径算法
DOI：
10.1145/3465084.3467945
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Russell, Katina
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
此简短公告介绍了 CONGEST 模型中具有非负实边权重的有向图的 (1+ε) 近似单源最短路径算法，该算法以 Õ ((n^1/2 +D+n^2/5+o(1) D^2/5 )log W / ε^2) 轮运行，其中 W 是最大和最小非零边权重之间的比率。
This brief announcement presents an algorithm for (1+ε) approximate single-source shortest paths for directed graphs with non-negative real edge weights in the CONGEST model that runs in Õ ((n^1/2 +D+n^2/5+o(1) D^2/5 )log W / ε^2) rounds, where W is the ratio between the largest and smallest non-zero edge weights.
登录
查看更多内容
改进工作跨度权衡单一源可达性和近似最短路径
DOI：
10.1145/3350755.3400222
发表时间：
2020
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
分布式和流式模型中的近最优近似最短路径和转运
DOI：
--
发表时间：
2016
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
R. Becker;Andreas Karrenbauer;Sebastian Krinninger;C. Lenzen
通讯作者：
C. Lenzen
几乎线性功和平方根深度的并行可达性
DOI：
10.1109/focs.2019.00098
发表时间：
2019
期刊：
Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Liu, Yang P.;Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron