A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents a parallel algorithm that computes the single source longest path problem on acyclic graphs G(V,A) with integer arc lengths on SIMD-SM-EREW parallel computers. The algorithm solves the problem in O(log^2(ln)) time, O((ln)^<2.376>) processors, and O((ln)^2) memory space, where n = |V| and the arc lengths are integers in the set {1,2,...,l}.For any constant l, our algorithm solves the single source longest path problem in O(log^2 n)time, O(n^<2.376>) processors, and O(n^2) memory space. Our algorithm is then used to derive O(log^2 n) time, O(n^<2.376>) processors, and O(n^2) memory space parallel algorithms for a number of problems, such as minimum coloring, maximum clique, and so on, of permutation graphs on an SIMD-SM-EREW computer.
- 一般社団法人情報処理学会の論文
- 1996-09-15
著者
-
Takaoka Tadao
Department Of Computer Science Ibaraki University
-
Takaoka Tadao
Department Of Computer Science University Of Ibaraki
-
GU QIAN-PING
Department of Computer Software, The University of Aizu
-
Gu Q‐p
Univ. Aizu.
-
Gu Qian-ping
Department Of Computer Software The University Of Aizu
-
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
- Efficient Algorithms for Node Disjoint Path Problems
- d-Separated Paths in Hypercubes and Star Graphs
- 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
- Distributed Algorithms for Leader Election on Partially Ordered Keys (特集 マルチメディア通信プロトコル)
- Fault Tolerant Routing in Toroidal Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Set-To-Set Fault Tolerant Routing in Star Graphs
- Efficient Broadcasting Algorithms in Faulty Hypercubes and Star Graphs
- Node-to-Set Disjoint Paths with Optimal Length in Star Graphs (Special Issue on Parallel and Distributed Supercomputing)
- Linear Time Algorithms for Fault Tolerant Routing in Hypercubes and Star Graphs
- 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