Efficient parallel algorithms for some graph problems

Abstract

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O (log ² n ) time bound can be achieved using only K = n ⌈ n /log ² n ⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.