Skip to main content
Journal cover image

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

Publication ,  Journal Article
Pan, V; Reif, J
Published in: Information Processing Letters
October 25, 1991

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.

Duke Scholars

Published In

Information Processing Letters

DOI

ISSN

0020-0190

Publication Date

October 25, 1991

Volume

40

Issue

2

Start / End Page

79 / 83

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Pan, V., & Reif, J. (1991). The parallel computation of minimum cost paths in graphs by stream contraction. Information Processing Letters, 40(2), 79–83. https://doi.org/10.1016/0020-0190(91)90013-8
Pan, V., and J. Reif. “The parallel computation of minimum cost paths in graphs by stream contraction.” Information Processing Letters 40, no. 2 (October 25, 1991): 79–83. https://doi.org/10.1016/0020-0190(91)90013-8.
Pan V, Reif J. The parallel computation of minimum cost paths in graphs by stream contraction. Information Processing Letters. 1991 Oct 25;40(2):79–83.
Pan, V., and J. Reif. “The parallel computation of minimum cost paths in graphs by stream contraction.” Information Processing Letters, vol. 40, no. 2, Oct. 1991, pp. 79–83. Scopus, doi:10.1016/0020-0190(91)90013-8.
Pan V, Reif J. The parallel computation of minimum cost paths in graphs by stream contraction. Information Processing Letters. 1991 Oct 25;40(2):79–83.
Journal cover image

Published In

Information Processing Letters

DOI

ISSN

0020-0190

Publication Date

October 25, 1991

Volume

40

Issue

2

Start / End Page

79 / 83

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences