BDBComp
Parceria:
SBC
Dual Ascent Distribuído para o Problema de Steiner On-Line

Marcelo SantosLúcia DrummondEduardo Uchoa

O Problema de Steiner consiste em minimizar o custo de uma arborescência que atinja um subconjunto de nós, ditos “terminais”, de um grafo a partir de um nó raiz r. No Problema de Steiner On-Line, o conjunto de terminais sofre alterações com o passar do tempo, podendo nós comuns entrar no conjunto de terminais e/ou terminais saírem deste conjunto, se transformando em nós comuns. A maioria dos algoritmos conhecidos para este problema atualmente usa técnicas simples para inclusão ou exclusão de terminais, utilizando algoritmos conhecidos para o problema estático periodicamente para reorganizações na árvore, levando a qualidades de solução superiores. Este trabalho apresenta uma heurística distribuída para o problema On-Line, baseada no algoritmo “Dual Ascent” proposto por [Wong 1984], que dispara reconstruções na árvore de distribuição de forma mais oportuna do que os principais algoritmos conhecidos atualmente.

http://www.lbd.dcc.ufmg.br/colecoes/sbrc/2009/022.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD