Efficient parallel algorithms for computing all pair shortest paths in directed graphs

Published

Journal Article

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 Authors

Cited Authors

  • Han, Y; Pan, V; Reif, J

Published Date

  • December 1, 1992

Published In

  • 4th Annual Acm Symposium on Parallel Algorithms and Architectures

Start / End Page

  • 353 - 362

Citation Source

  • Scopus