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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A fast graph search multiprocessor algorithm


    Contributors:


    Publication date :

    1997-01-01


    Size :

    821921 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    A Fast Graph Search Multi-processor Algorithm

    Cheng, K.-H. / Venkata Subramaniam, P. K. / IEEE | British Library Conference Proceedings | 1997


    Two-Point Flight Path Planning Using A Fast Graph-Search Algorithm

    Wen-Ying Chang / Fei-Bin Hsiao / Donglong Sheu | AIAA | 2006


    Fast spherical search algorithm

    Liebe, Carl Christian | NTRS | 2004


    Fast spherical search algorithm

    Liebe, C.C. | IEEE | 2004


    7.1305 Fast Spherical Search Algorithm

    IEEE | British Library Conference Proceedings | 2004