Lúcia M.A. Drummond, Eduardo Uchoa, Alexandre D. Gonçalves, Juliana M.N.
Silva, Marcelo C.P.Santos and Maria Clícia S. de Castro
This work introduces a distributed branch-and-bound algorithm to be run on
computational Grids. Grids are often organized in a hierarchical fashion: clusters of
processors connected via high-speed links, while the clusters themselves are
geographically distant and connected through slower links. Our algorithm does not
employ the usual master-worker paradigm and it considers the hierarchical structure of
Grids in its load balance and fault tolerance procedures. This algorithm was applied over
an existing code for the Steiner Problem in graphs. Experiments on real Grid conditions
have demonstrated its efficiency and scalability.