Marcelo Santos,  Lúcia Drummond,  Eduardo 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

Processando consulta.