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

DOI10.1016/0020-0190(91)90013-8zbMath0748.68025OpenAlexW2063204215MaRDI QIDQ1183440

Pan, Victor Y., John H. 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)

Related Items

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

Cites Work

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