A fast graph search multiprocessor algorithm

A systematic exploration of the vertices of a graph is the graph search problem. In this paper, we propose a new multiprocessor algorithm to solve the graph search problem. Our approach is to divide the work into three logical tasks, each carried out by a different group of processors. The first group processes the information of vertices. The second group balances the work-load among the first group of processors dynamically, and the third group processes the relationships among the vertices of the graph. They remove edges leading to processed vertices, thus eliminating the possibility of duplication of processing. Our proposed algorithm takes O(n/p+L) time using reconfigurable meshes with O(pl) processors, where n is the number of vertices, l the number of edges, and L is one plus the minimum distance of the furthest vertex from the start vertex. Our algorithm is faster than the parallel breadth-first search algorithm on a SIMD-SM-R model