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.
A fast graph search multiprocessor algorithm
1997-01-01
821921 byte
Conference paper
Electronic Resource
English
A Fast Graph Search Multi-processor Algorithm
British Library Conference Proceedings | 1997
|Fast spherical search algorithm
NTRS | 2004
|Fast spherical search algorithm
IEEE | 2004
|7.1305 Fast Spherical Search Algorithm
British Library Conference Proceedings | 2004
|