A heuristic approximation algorithm for the Steiner tree based on prior multicast nodes Online publication date: Wed, 01-Aug-2018
by Weijun Yang; Yun Zhang; Yuanfeng Chen; Jianqi Liu; Genyi Liu
International Journal of Autonomous and Adaptive Communications Systems (IJAACS), Vol. 11, No. 3, 2018
Abstract: Multicast routing is regarded as a critical component in networks, especially the real-time applications for multimedia become increasingly popular. Finding such a Steiner tree in multicast routing is an NP-complete problem as for as we know. This paper devises a novel and improved prior nodes minimum cost path heuristic approximation algorithm (IPNMPH) to deal with it. Some paths passing through adjusted prior destination nodes are selected, and they partly share links in the network and decrease the cost of the multicast routing tree. The theoretical validations for the proposed algorithm show that its approximation ratio is 2(1 - 1/q) and the time complexity is O(n3). The simulation experiments on special networks for the proposed algorithm are presented to show its performance and efficiency, and the results indicate that the cost of the IPNMPH algorithm is superior to previous algorithms in most cases.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Autonomous and Adaptive Communications Systems (IJAACS):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook