Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1
Publication
, Journal Article
Han, Y; Pan, VY; Reif, JH
Published in: Algorithmica (New York)
January 1, 1997
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 CCRW 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
Algorithmica (New York)
DOI
ISSN
0178-4617
Publication Date
January 1, 1997
Volume
17
Issue
4
Start / End Page
399 / 415
Related Subject Headings
- Computation Theory & Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Han, Y., Pan, V. Y., & Reif, J. H. (1997). Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1. Algorithmica (New York), 17(4), 399–415. https://doi.org/10.1007/BF02523680
Han, Y., V. Y. Pan, and J. H. Reif. “Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1.” Algorithmica (New York) 17, no. 4 (January 1, 1997): 399–415. https://doi.org/10.1007/BF02523680.
Han Y, Pan VY, Reif JH. Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1. Algorithmica (New York). 1997 Jan 1;17(4):399–415.
Han, Y., et al. “Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1.” Algorithmica (New York), vol. 17, no. 4, Jan. 1997, pp. 399–415. Scopus, doi:10.1007/BF02523680.
Han Y, Pan VY, Reif JH. Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1. Algorithmica (New York). 1997 Jan 1;17(4):399–415.
Published In
Algorithmica (New York)
DOI
ISSN
0178-4617
Publication Date
January 1, 1997
Volume
17
Issue
4
Start / End Page
399 / 415
Related Subject Headings
- Computation Theory & Mathematics