Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths
Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths
复制标题
改进工作跨度权衡单一源可达性和近似最短路径
DOI：
10.1145/3350755.3400222
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Russell, Katina
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
这个简短的公告提出了并行算法之间的工作和跨度的单源可达性和有向图上的近似最短路径的折衷。这两个算法都有~O（mρ2+ nρ4）的工作时间，并且对所有ρ ∈ [1，<$n]都有n1/2+ o（1）/ρ span.
This brief announcement presents parallel algorithms with a tradeoff between work and span for single source reachability and approximate shortest paths on directed graphs. Both algorithms have ~O(mρ2+ nρ4) work and achieve n1/2+ o(1)/ρ span for all ρ ∈ [1,√n].
登录
查看更多内容
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
DOI：
10.1006/jagm.1997.0888
发表时间：
1997
期刊：
J. Algorithms
影响因子：
--
作者：
P. Klein;Sairam Subramanian
通讯作者：
Sairam Subramanian
并行算法的时间与工作权衡
DOI：
10.1145/265910.265923
发表时间：
1997
期刊：
J. ACM
影响因子：
--
作者：
T. Spencer
通讯作者：
T. Spencer
几乎线性功和平方根深度的并行可达性
DOI：
10.1109/focs.2019.00098
发表时间：
2019
期刊：
Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Liu, Yang P.;Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron