The parallel computation of minimum cost paths in graphs by stream contraction


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • October 25, 1991

Published In

Volume / Issue

  • 40 / 2

Start / End Page

  • 79 - 83

International Standard Serial Number (ISSN)

  • 0020-0190

Digital Object Identifier (DOI)

  • 10.1016/0020-0190(91)90013-8

Citation Source

  • Scopus