Algoritmos Paralelos Distribuidos para Búsquedas en Profundidad sobre Grafos

Federico Fapitalle, Gustavo E, Vazquez, Ignacio Ponzoni, Nélida B. Brignole


A descentralized parallel-distributed algorithm to carry out depth-first searches along graphs is presented. The method is based on a new parallel-distributed architecture that is proposed in this article. In this formulation the computing tasks are distrIbuted among three kind of nodes: the Master, the Supervisors and the Workers. The Master organizes the distribution of the various search subspaces among the Supervisors. In turn, each Supervisor delegates the exploration of the subpaths inside the assigned subspace to the Workers under its control. So, each Worker explores a given part of the search space, sending its Supervisor information about the subpaths it could find.
Finally, the Supervisor has to recombine its own subpaths with those stored by the other Supervisors. The new algorithm was implemented in C using the PVM messagepassage library and its performance was evaluated in terms· of speed-up and efficiency.

Full Text:


Asociación Argentina de Mecánica Computacional
Güemes 3450
S3000GLN Santa Fe, Argentina
Phone: 54-342-4511594 / 4511595 Int. 1006
Fax: 54-342-4511169
E-mail: amca(at)
ISSN 2591-3522