Publications [#236937] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Pan, V; Reif, J, The parallel computation of minimum cost paths in graphs by stream contraction, Information Processing Letters, vol. 40 no. 2 (October, 1991), pp. 79-83, Elsevier BV, ISSN 0020-0190 [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   We accelerate by a factor of log n and with no increase of the processor bound our previous parallel algorithm for path algebra computation in the case of the minimum cost path computation in an n-vertex graph and, more generally, wherever the path algebra has an order relation defined by its ⊕ operation. The acceleration is obtained by means of a novel technique of stream contraction. © 1991.