A Parallel Algorithm for the Stack Breadth-First Search(Regular Section)

スポンサーリンク

概要

• 論文の詳細を見る

• Parallelization of the P-complete problem is known to be difficult. In this paper, we consider the parallelizability of a stack breadth-first search (stack BFS) problem, which is proved to be P-complete. We first propose the longest path length (LPL) as a measure for the P-completeness of the stack BFS. Next, using this measure, we propose an efficient parallel algorithm for the stack BFS. Assuming the size and LPL of an input graph are n and l, respectively, the complexity of the algorithm indicates that the stack BFS is in the class NC^k+1 if l = O(log^k n), where k is a positive integer. In addition, the algorithm is cost optimal if l = O(n^E), where 0 < E < 1.

• 社団法人電子情報通信学会の論文
• 2002-12-01

著者

• Nakashima Takaaki

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

• Fujiwara Akihiro

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

関連論文

• Polynomially Fast Parallel Algorithms for Some P-Complete Problems (Special Section on Discrete Mathematics and Its Applications)
• Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
• Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points (Special Section on Discrete Mathematics and Its Applications)
• A Parallel Algorithm for the Stack Breadth-First Search(Regular Section)

スポンサーリンク