Parallel algorithms for the single source shortest path problem

DOI10.1007/BF02254849zbMath0479.68068OpenAlexW2793079MaRDI QIDQ1162156

Prabhaker Mateti, Narsingh Deo

Publication date: 1982

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02254849

zbMATH Keywords

parallelizationgraph algorithmscorrectness proofsdesign principlesarray processorsMIMD machinesnetwork of processorsmultiple-instruction multiple-data stream machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Specification and verification (program logics, model checking, etc.) (68Q60) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Related Items

Prallel algorithms for analyzing activity networks ⋮ Parallel algorithm for analysing activity networks on a tree-structured computer ⋮ Algorithms for some graph problems on a distributed computational model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The temporal semantics of concurrent programs
• Shortest-path algorithms: Taxonomy and annotation
• Computing connected components on parallel computers
• A parallel algorithm for constructing minimum spanning trees
• Algorithm 562: Shortest Path Lengths [H]
• A New Approach to Proving the Correctness of Multiprocess Programs
• Verifying properties of parallel programs
• Formal verification of parallel programs
• Parallel Computations in Graph Theory
• A Note on Dijkstra's Shortest Path Algorithm