Distributed Dual Ascent Algorithm for Steiner Problems in Networks

Marcelo SantosLúcia DrummondEduardo Uchoa

Steiner Problems in undirected or directed graphs are often used to model multicast routing problems. The directed case being particularly suitable to situations where most of the trafic has a single source. Sequential Steiner heuristics are not convenient in that context, since one can not assume that a central node has complete information about the topology and the state of a large wide area network. This work presents a distributed version of the Dual Ascent Heuristic proposed by Wong, known for its remarkable good practical results, lower and upper bounds, in both undirected and directed Steiner problems. The distributed Dual Ascent has worst case complexities of O(|V |2) time and O(|T|.|V |2) messages. Experimental results are also presented, showing the eficiency of the proposed algorithm.

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:
     Mantida por: