
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.

Improvement of Steiner Tree Algorithm: BranchBased MultiCast
Hiroshi MATSUURA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.12
pp.27432752 Publication Date: 2013/12/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.2743
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Fundamentals of Information Systems Keyword: Steiner tree, MPH, BBMC, multicast tree,
Full Text: PDF(1016.2KB)>>
Summary:
There is a well known Steiner tree algorithm called minimumcost paths heuristic (MPH), which is used for many multicast network operations and is considered a benchmark for other Steiner tree algorithms. MPH's average case time complexity is O(m(l+nlog n)), where m is the number of end nodes, n is the number of nodes, and l is the number of links in the network, because MPH has to run Dijkstra's algorithm as many times as the number of end nodes. The author recently proposed a Steiner tree algorithm called branchbased multicast (BBMC), which produces exactly the same multicast tree as MPH in a constant processing time irrespective of the number of multicast end nodes. However, the theoretical result for the average case time complexity of BBMC was expressed as O(log m(l+nlog n)) and could not accurately reflect the above experimental result. This paper proves that the average case time complexity of BBMC can be shortened to O(l+nlog n), which is independent of the number of end nodes, when there is an upper limit of the node degree, which is the number of links connected to a node. In addition, a new parameter β is applied to BBMC, so that the multicast tree created by BBMC has less links on it. Even though the tree costs increase due to this parameter, the tree cost increase rates are much smaller than the link decrease rates.

