Efficient parallel algorithms for computing all pair shortest paths in directed graphs

DOI10.1007/BF02523680zbMath0869.68053OpenAlexW2033740214MaRDI QIDQ676269

Yijie Han, John H. Reif, Pan, Victor Y.

Publication date: 20 August 1997

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathsdirected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

External matrix multiplication and all-pairs shortest path

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• The parallel computation of minimum cost paths in graphs by stream contraction
• A new upper bound on the complexity of the all pairs shortest path problem
• Fast and efficient solution of path algebra problems
• Binary Trees and Parallel Scheduling Algorithms
• Probabilistic Parallel Algorithms for Sorting and Selection
• Parallel Matrix and Graph Algorithms
• Parallelism in Comparison Problems
• New Bounds on the Complexity of the Shortest Path Problem
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Work-Preserving Speed-Up of Parallel Matrix Computations