The P-complete problem is known as a problem which is hard to be parallelized. In this paper, we consider parallelizability of a stack breadth-first search (stack BFS) problem, which is proved to be P-complete. First we prove that the stack BFS is P-complete even if the maximum degree of an input graph is 3. Next we propose the longest path length (LPL) as a measure for P-completeness of the stack BFS. Using the measure, we propose an efficient parallel algorithm for the stack BFS. Assuming the size and LPL of an input graph is n and l respectively, the complexity of the algorithm shows that the stack BFS is in NC if l = O(log{sup}kn) where k is a positive integer. In addition to this, the algorithm is cost optimal if l = O(n{sup}ε) where 0＜ε＜1.
展开▼
