
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

MultiAgent Steiner Tree Algorithm Based on BranchBased Multicast
Hiroshi MATSUURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E99D
No.11
pp.27452758 Publication Date: 2016/11/01 Publicized: 2016/08/08 Online ISSN: 17451361
DOI: 10.1587/transinf.2015EDP7417 Type of Manuscript: PAPER Category: Artificial Intelligence, Data Mining Keyword: Steiner tree, GA, PSO, multicast tree,
Full Text: PDF>>
Summary:
The Steiner tree problem is a nondeterministicpolynomialtimecomplete problem, so heuristic polynomialtime algorithms have been proposed for finding multicast trees. However, these polynomialtime algorithms' treecost 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 polynomialtime algorithms. However, these intelligence algorithms are timeconsuming, even though they can reach quasioptimal multicast trees. This paper proposes the multiagent branchbased multicast (BBMC) algorithm, which can maintain the fast speed of polynomialtime algorithms while matching the treecost optimality of intelligence algorithms. The advantage of the proposed multiagent BBMC algorithm is its covering of discarded effective branch candidates to seek the optimal multicast tree. By saving these branch candidates, the algorithm incurs treecosts 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.

