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

DOI10.1016/0020-0190(91)90013-8MaRDI QIDQ1183440zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan, J. Reif

Publication date 28 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90013-8

zbMATH Keywords

path algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 56471
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• Parallel nested dissection for path algebra computations
• scientific article; zbMATH DE number 1186513
• Efficient parallel algorithms for the minimum cost flow problem

Cites work

• An Algebra for Network Routing Problems
• Dioïds and semirings: Links to fuzzy sets and other applications
• Fast and efficient parallel solution of dense linear systems
• Fast and efficient solution of path algebra problems
• Regular Algebra Applied to Path-finding Problems

Cited in

(4)

• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Efficient parallel factorization and solution of structured and unstructured linear systems
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Efficient parallel algorithms for computing all pair shortest paths in directed graphs

This page was built for publication: The parallel computation of minimum cost paths in graphs by stream contraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183440)