An O(n(n^2/p+log p)) Parallel Algorithm to Compute the All Pairs Shortest Paths and the Transitive Closure

スポンサーリンク

概要

• 論文の詳細を見る

• Multiprocessors with shared memory structured as a complete binary tree are considered for use with a parallel algorithm to compute the all pairs shortest paths and the reflexive transitive closure in a weighted directed graph. The time complexity of the parallel algorithm is O(n(n^2/(p)+logp)), where n is the number of vertices in the graph and p(≤n^2) is the number of processors used. The Ada language is used to implement the algorithm.

• 一般社団法人情報処理学会の論文
• 1989-08-30

著者

• Takaoka Tadao

  Department Of Computer Science Ibaraki University

• Jun Ma

  Department Of Computer Science Ibaraki University

• Takaoka Tadao

  Department of Computer Science and Software Engineering University of Canterbury

関連論文

• A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
• A Systematic Approach to Parallel Program Verification
• On Improving the Average Case of the Boyer-Moore String Matching Algorithm
• Parallel Algorithms for a Class of Graph Theoretic Problems
• The Extension of the Aho-Corasick Algorithm to Multiple Rectangular Pattern Arrays of Different Sizes and N-Dimensional Cases
• Entropy as Computational Complexity
• An O(n(n^2/p+log p)) Parallel Algorithm to Compute the All Pairs Shortest Paths and the Transitive Closure

スポンサーリンク