Skip to main content
construction release_alert
The Scholars Team is working with OIT to resolve some issues with the Scholars search index
cancel
Journal cover image

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.
Journal cover image

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