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

Authors: Weijun Yang; Yun Zhang; Yuanfeng Chen; Jianqi Liu; Genyi Liu

Addresses: Department of Electromechanical Engineering, Guangzhou City Polytechnic, Guangzhou, China ' Faculty of Automation, Guangdong University of Technology, Guangzhou, China ' Department of Electromechanical Engineering, Guangzhou City Polytechnic, Guangzhou, China ' School of Information Engineering, Guangdong Mechanical and Electrical College, Guangzhou, China ' School of Information Engineering, Guangdong Mechanical and Electrical College, Guangzhou, China

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(n³). 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.

Keywords: multicast routing; Steiner tree; approximation algorithm; prior nodes.

DOI: 10.1504/IJAACS.2018.093690

International Journal of Autonomous and Adaptive Communications Systems, 2018 Vol.11 No.3, pp.193 - 208

Received: 19 May 2016
Accepted: 21 Nov 2016
Published online: 01 Aug 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article