Publications [#237129] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Han, Y; Pan, VY; Reif, JH, Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs1, Algorithmica New York, vol. 17 no. 4 (January, 1997), pp. 399-415, Springer Nature [doi]
   (last updated on 2026/01/13)

   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 CCRW 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.