Parallel Depth-First Search on Clusters of Workstations

VAZQUEZ, GUSTAVO E.; PONZONI, IGNACIO; BRIGNOLE, NÉLIDA B.

Atlanta, Georgia, Estados Unidos

Conferencia; SIAM Annual Meeting 1999; 1999

SIAM (Society for Industrial and Applied Mathematics)

In this work we present several algorithms based on domain decom­position techniques to carry out depth-first searches along undirected graphs on distributed computing environments. The algorithms were implemented using PVM as message-passing library. Their perfor­mance was compared in terms of speed-up and efficiency. The analysis was developed with a view to choosing the most convenient parallel technique for the structural rearrangement of large-size sparse matri­ces to special forms useful for engineering applications.