A Parallel Algorithm for the Stack Breadth-First Search

Takaaki NAKASHIMA; Akihiro FUJIWARA

A Parallel Algorithm for the Stack Breadth-First Search

Takaaki NAKASHIMA, Akihiro FUJIWARA

Full Text Views

0

Cite this

Summary :

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^ε), where 0 < ε < 1.

Publication: IEICE TRANSACTIONS on Information Vol.E85-D No.12 pp.1955-1958

Publication Date: 2002/12/01

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: Computational Complexity Theory

Cite this

Copy

Takaaki NAKASHIMA, Akihiro FUJIWARA, "A Parallel Algorithm for the Stack Breadth-First Search" in IEICE TRANSACTIONS on Information, vol. E85-D, no. 12, pp. 1955-1958, December 2002, doi: .
Abstract: 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^ε), where 0 < ε < 1.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_12_1955/_p

Copy

@ARTICLE{e85-d_12_1955,
author={Takaaki NAKASHIMA, Akihiro FUJIWARA, },
journal={IEICE TRANSACTIONS on Information},
title={A Parallel Algorithm for the Stack Breadth-First Search},
year={2002},
volume={E85-D},
number={12},
pages={1955-1958},
abstract={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^ε), where 0 < ε < 1.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - A Parallel Algorithm for the Stack Breadth-First Search
T2 - IEICE TRANSACTIONS on Information
SP - 1955
EP - 1958
AU - Takaaki NAKASHIMA
AU - Akihiro FUJIWARA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2002
AB - 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^ε), where 0 < ε < 1.
ER -