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

DOI10.1007/BF02523680MaRDI QIDQ676269zbMATH OpenOpenAlexFDO

Authors Yijie Han, J. Reif, Victor Y. Pan

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

directed graphsshortest paths

Mathematics Subject Classification ID

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

Recommendations

• A sharper analysis of a prallel algorithm for the all pairs shortest path problem
• scientific article; zbMATH DE number 62663
• Efficient parallel algorithms for path problems in directed graphs
• Subcubic cost algorithms for the all pairs shortest path problem

Cites work

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

Cited in

(10)

• Efficient parallel algorithms for path problems in directed graphs
• Improved processor bounds for parallel algorithms for weighted directed graphs
• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• External matrix multiplication and all-pairs shortest path
• scientific article; zbMATH DE number 56471 (Why is no real title available?)
• scientific article; zbMATH DE number 62663 (Why is no real title available?)
• scientific article; zbMATH DE number 7266346 (Why is no real title available?)
• Computational Science – ICCS 2005
• A sharper analysis of a prallel algorithm for the all pairs shortest path problem

This page was built for publication: Efficient parallel algorithms for computing all pair shortest paths in directed graphs

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