Dynamic Multicast can be modeled by the On-Line Steiner Problem,which consists in finding a minimum cost tree that reaches a subset of nodes of agraph, called terminals, from a root node r, where the terminals set can changeover time, with nodes entering or leaving this set. Most of the known algorithmsfor this problem apply simple approaches for inclusion and exclusion operations,and known static algorithms to reorganize the tree periodically. This paperpresents a new heuristic for the On-Line Steiner Problem, based on the previouslyproposed distributed Dual-Ascent algorithm, that triggers reorganizationsmore opportunistically than the main known heuristics for the problem. In orderto analyze the proposed algorithm, another heuristic frequently employedin the literature as a baseline for comparison with other works, Aries, was alsoimplemented. Experimental results showed that the new On-Line distributedversion of Dual-Ascent outperformed Aries in terms of quality of solutions andcomputational effort.

http://www.lbd.dcc.ufmg.br/colecoes/sbrc/2010/0063.pdf

Rafaelli de Carvalho Coutinho,
Ubiratam Carvalho de Paula Junior,
Diego Passos,
Célio Albuquerque,
Lúcia M. A. Drummond.

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

Dynamic Multicast can be modeled by the On-Line Steiner Problem,which consists in finding a minimum cost tree that reaches a subset of nodes of agraph, called terminals, from a root node r, where the terminals set can changeover time, with nodes entering or leaving this set. Most of the known algorithmsfor this problem apply simple approaches for inclusion and exclusion operations,and known static algorithms to reorganize the tree periodically. This paperpresents a new heuristic for the On-Line Steiner Problem, based on the previouslyproposed distributed Dual-Ascent algorithm, that triggers reorganizationsmore opportunistically than the main known heuristics for the problem. In orderto analyze the proposed algorithm, another heuristic frequently employedin the literature as a baseline for comparison with other works, Aries, was alsoimplemented. Experimental results showed that the new On-Line distributedversion of Dual-Ascent outperformed Aries in terms of quality of solutions andcomputational effort.

http://www.lbd.dcc.ufmg.br/colecoes/sbrc/2010/0063.pdf

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