Efficient parallel algorithms for computing all pair shortest paths in directed graphs
Publication
, Journal Article
Han, Y; Pan, V; Reif, J
Published in: 4th Annual ACM Symposium on Parallel Algorithms and Architectures
January 1, 1992
We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexity O(f(n)/p + I(n)log n) on the PRAM using p processors, where I(n) is log n on the EREW PRAM, log log n on the CRCW PRAM, f(n) is o(n3). On the randomized CRCW PRAM we are able to achieve time complexity O(n3/p + log n) using p processors.
Duke Scholars
Published In
4th Annual ACM Symposium on Parallel Algorithms and Architectures
DOI
Publication Date
January 1, 1992
Start / End Page
353 / 362
Citation
APA
Chicago
ICMJE
MLA
NLM
Han, Y., Pan, V., & Reif, J. (1992). Efficient parallel algorithms for computing all pair shortest paths in directed graphs. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 353–362. https://doi.org/10.1145/140901.141913
Han, Y., V. Pan, and J. Reif. “Efficient parallel algorithms for computing all pair shortest paths in directed graphs.” 4th Annual ACM Symposium on Parallel Algorithms and Architectures, January 1, 1992, 353–62. https://doi.org/10.1145/140901.141913.
Han Y, Pan V, Reif J. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. 4th Annual ACM Symposium on Parallel Algorithms and Architectures. 1992 Jan 1;353–62.
Han, Y., et al. “Efficient parallel algorithms for computing all pair shortest paths in directed graphs.” 4th Annual ACM Symposium on Parallel Algorithms and Architectures, Jan. 1992, pp. 353–62. Scopus, doi:10.1145/140901.141913.
Han Y, Pan V, Reif J. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. 4th Annual ACM Symposium on Parallel Algorithms and Architectures. 1992 Jan 1;353–362.
Published In
4th Annual ACM Symposium on Parallel Algorithms and Architectures
DOI
Publication Date
January 1, 1992
Start / End Page
353 / 362