Paper Info
Title
Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths
Abstract
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].
Year
DOI
Venue
2020
10.1145/3350755.3400222
SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures Virtual Event USA July, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-6935-0
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Nairen Cao101.35
Jeremy T. Fineman258736.10
Katina Russell301.35