Algoritmos Paralelos Distribuidos para Búsquedas en Profundidad sobre Grafos

Abstract

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.