Paper Info
Title
Parallel Shortest Paths with Negative Edge Weights
Abstract
BSTRACTThis 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.
Year
DOI
Venue
2022
10.1145/3490148.3538583
ACM Symposium on Parallel Algorithms and Architectures
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Nairen Cao101.35
Jeremy T. Fineman258736.10
Katina Russell301.35