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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A fast graph search multiprocessor algorithm


    Beteiligte:


    Erscheinungsdatum :

    01.01.1997


    Format / Umfang :

    821921 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    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