Title :
The parallel complexity of queue versus stack breadth-first search
Author :
Greenlaw, Raymond
Author_Institution :
Dept. of Comput. Sci., New Hampshire Univ., Durham, NH, USA
Abstract :
Two algorithms for breadth-first search (BFS) are analyzed with respect to their parallel complexities. The stack (queue) BFS algorithm uses a stack (queue) as its underlying data structure. A natural decision problem based on stack BFS is proved P-complete, indicating the algorithm is inherently sequential. The proof technique used in the reduction is new. This theorem sharply contrasts a result the author presents showing that queue BFS is in NC, indicating the queue implementation is highly parallelizable. The significance of these results is due to the fundamental importance of BFS and due to their complementary nature
Keywords :
computational complexity; data structures; parallel algorithms; search problems; P-complete; data structure; natural decision problem; parallel complexities; parallel complexity; queue; stack breadth-first search; Algorithm design and analysis; Circuits; Complexity theory; Computer science; Data structures; Graphics; Partitioning algorithms; Sorting;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143654
