Multi-Agent Steiner Tree Algorithm Based on Branch-Based Multicast

Hiroshi MATSUURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.11   pp.2745-2758
Publication Date: 2016/11/01
Publicized: 2016/08/08
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDP7417
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword: 
Steiner tree,  GA,  PSO,  multicast tree,  

Full Text: PDF>>
Buy this Article



Summary: 
The Steiner tree problem is a nondeterministic-polynomial-time-complete problem, so heuristic polynomial-time algorithms have been proposed for finding multicast trees. However, these polynomial-time algorithms' tree-cost optimality rates are not sufficient to obtain effective multicast trees, so intelligence algorithms, such as the genetic algorithm and artificial fish swarm algorithm, were proposed to improve previously proposed polynomial-time algorithms. However, these intelligence algorithms are time-consuming, even though they can reach quasi-optimal multicast trees. This paper proposes the multi-agent branch-based multicast (BBMC) algorithm, which can maintain the fast speed of polynomial-time algorithms while matching the tree-cost optimality of intelligence algorithms. The advantage of the proposed multi-agent BBMC algorithm is its covering of discarded effective branch candidates to seek the optimal multicast tree. By saving these branch candidates, the algorithm incurs tree-costs that are as small as those of intelligence algorithms, and by saving only a limited number of effective candidates, the algorithm is much faster than intelligence algorithms.