
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.

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