Um algoritmo branch-and-bound distribuído para o Problema de Steiner em Grafos para execução em Grids

Detalhes bibliográficos
Ano de defesa: 2008
Autor(a) principal: Gonçalves, Alexandre Domingues
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Programa de Pós-Graduação em Computação
Computação
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://app.uff.br/riuff/handle/1/17810
Resumo: Esta dissertação apresenta um algoritmo branch-and-bound distribuído para execução em Grids computacionais. Geralmente as grids são organizadas de modo hierárquico: processadores de um mesmo cluster são conectados através de links de alta velocidade, enquanto os clusters são geograficamente distantes entre si e se conectam através de links de baixa velocidade. O algoritmo apresentado não emprega o paradigma usual de mestre-escravo e leva em consideração a estrutura hierárquica das Grids no balanceamento de carga e procedimentos de tolerância a falhas. Este algoritmo foi aplicado sobre um código existente para resolver o Problema de Steiner em Grafos. Experimentos em condições reais de Grid demonstraram sua eficiência e escalabilidade