Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

摘要

Using an exclusive-read and exclusive-write (EREW) parallel random-access memory (PRAM) model with a fixed number of processors, optimal parallel algorithms are presented for several problems on undirected graphs. These problems include finding the connected components, a spanning forest, a fundamental cycle set, the bridges, and checking bipartiteness of a given graph. The algorithms for computing the connected components and a spanning forest are designed using the divide-and-conquer strategy and are used in turn to design efficient algorithms for the remaining three problems. Each of the algorithms achieves optimal speedup for dense as well as sparse graphs, and is optimally scalable up to a certain number of processors. A lower bound on the processor-(time)/sup 2/ product for each algorithm is derived. The input graph is represented by an unordered list of edges, and the use of simple and elegant data structures avoids memory read-conflicts or write-conflicts.