A heuristic approximation algorithm for the Steiner tree based on prior multicast nodes

作者：Yang Weijun; Zhang Yun; Chen Yuanfeng; Liu Jianqi; Liu Genyi

来源：International Journal of Autonomous and Adaptive Communications Systems, 2018, 11(3): 193-208.

DOI：10.1504/IJAACS.2018.093690

• Approximation ratios
• Heuristic approximation algorithms
• Minimum cost paths
• Multicast routing
• Prior nodes
• Real-time application
• Steiner trees
• Theoretical validations

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.

• 出版日期2018