Publications [#236945] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. 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 (January, 1992), pp. 353-362 [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   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(n³). On the randomized CRCW PRAM we are able to achieve time complexity O(n³/p + log n) using p processors.