Paper Info
Title
The parallel complexity of queue versus stack breadth-first search
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.
Year
DOI
Venue
1990
10.1109/SPDP.1990.143654
Dallas, TX
Keywords
Field
DocType
p complete,queue,computer science,circuits,graphics,decision problem,parallel algorithms,data structures,algorithm design and analysis,breadth first search,computational complexity,sorting,data structure
Data structure,Algorithm design,Parallel algorithm,Computer science,Queue,Parallel computing,Breadth-first search,Algorithm,P-complete,Priority queue,Distributed computing,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
0-8186-2087-0
0
0.34
References 
Authors
7
1
Name
Order
Citations
PageRank
Raymond Greenlaw114218.56