Steiner tree heuristic algorithm based on weighted node

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (12): 3414-3416.

• Network and communications • Previous Articles Next Articles

Steiner tree heuristic algorithm based on weighted node

WANG Xiaolong,ZHAO Lifeng

School of Natural Sciences, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023,China

Received:2014-06-25 Revised:2014-08-24 Online:2014-12-01 Published:2014-12-31
Contact: WANG Xiaolong

基于加权节点的Steiner树启发式算法

王小龙,赵礼峰

南京邮电大学理学院,南京 210023

通讯作者: 王小龙
作者简介:赵礼峰(1959-),男,安徽淮北人,教授,主要研究方向:图论及其应用、网络流算法;王小龙(1989-),男,河南新乡人,硕士研究生,主要研究方向:图论及其应用、网络流算法。

Abstract

Abstract:

Minimum Steiner tree problem is a NP complete problem, and widely used in communication network point to multi-point routing. In order to realize more link sharing, reduce the cost of the desired Steiner tree, an algorithm named NWMPH (Node Weight based Minimum cost Path Heuristic) was proposed to solve the Steiner tree based on weighted node. The algorithm constructed a weighted formula of nonregular points, for each nonregular point weighting value. According to the weights of modifying the link cost. By modifying the cost shortest path in order to connect all regular points, get the minimum tree containing all regular points. For part of the data to calculate STEINLIB standard data set, the results show that: NWMPH algorithm and MPH algorithm used basically the same time. The cost of NWMPH algorithm to get Steiner tree is less than that of MPH algorithm. NWMPH algorithm uses less time and costs less to get Steiner tree than KBMPH algorithm.

摘要：

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明: NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法；NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。

CLC Number:

TP393.2

WANG Xiaolong ZHAO Lifeng. Steiner tree heuristic algorithm based on weighted node[J]. Journal of Computer Applications, 2014, 34(12): 3414-3416.

王小龙赵礼峰. 基于加权节点的Steiner树启发式算法[J]. 计算机应用, 2014, 34(12): 3414-3416.

References

［1］KARP R M. Complexity of computer computations［J］. Reducibility Among Combinatorial Problems, 1972, 23(1): 85-103.
［2］HAKIMI S L. Steiners problem in graphs and its implications［J］. Networks, 1971, 1(2): 113-133.
［3］DREYFUS S E, WAGNER R A. The Steiner problem in graphs［J］. Networks, 1971, 1(3): 195-207.
［4］BEASLEY J E. An SST-based algorithm for the Steiner problem in graphs［J］. Networks, 1989, 19(1): 1-16.
［5］KOU L, MARKOWSKY G, BERMAN L. A fast algorithm for Steiner trees［J］. Acta Informatica, 1981, 15(2): 141-145.
［6］TAKAHASHI H, MATSUYAMA A. An approximate solution for the Steiner problem in graphs［J］. Math Japonica, 1980, 24(6): 573-577.
［7］RAYWARD-SMITH V J, CLARE A. On finding Steiner vertices［J］. Networks, 1986, 16(3): 283-294.
［8］YU Y, QIU P. An improved Steiner tree heuristic algorithm［J］. Journal of communications, 2002, 23(11) : 35-40.(余燕平, 仇佩亮. 一种改进的Steiner树启发式算法［J］. 通信学报, 2002, 23(11): 35-40.)
［9］GUO W, XI Y, QUAN Y. Heuristic evolutionary programming to solve the Steiner tree problem［J］. Journal of Shanghai Jiao Tong University, 2001, 35(8) : 1152-1154.(郭伟, 席裕庚, 全亚斌. 启发式进化规划求解Steiner树问题［J］. 上海交通大学学报, 2001, 35(8): 1152-1154.)
［10］YANG N, HU Y. Steiner tree heuristic algorithm based on weight［C］// Proceedings of the 2nd International Conference on Future Computer and Communication. Piscataway: IEEE, 2010, 3: 415-418.
［11］YANG N. Application layer multicast and Steiner algorithm research［D］. Dalian: Dalian University of Technology, 2010.(杨宁. 应用层多播与Steiner算法的研究［D］. 大连: 大连理工大学, 2010.)
［12］BEASLEY J E. OR-Library: distributing test problems by electronic mail［J］. Journal of the Operational Research Society, 1990, 41(11): 1069-1072.

[1]	. Controller deployment and switch dynamic migration strategy in software-defined WAN [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	JIANG Bingcheng, HE Qian, CHEN Yiting, LIU Peng. Cloud database oriented attribute based encryption and query translation middleware [J]. Journal of Computer Applications, 2018, 38(8): 2280-2286.
[3]	ZHOU Qiao, YI Peng, MEN Haosong. Virtual network function backup method based on resource utility maximization [J]. Journal of Computer Applications, 2017, 37(4): 948-953.
[4]	YAUN Ying, WANG Cong, WANG Cuirong, SONG Xin, LYU Yanxia. Virtual network embedding algorithm for dynamic virtual network requests [J]. Journal of Computer Applications, 2017, 37(1): 6-11.
[5]	LIU Bangzhou, WANG Binqiang, WANG Wenbo, WU Di. Domain partition and controller placement for large scale software defined network [J]. Journal of Computer Applications, 2016, 36(12): 3239-3243.
[6]	LU Haoyang, CHEN Shiping. Resource allocation framework based on cloud computing package cluster mapping [J]. Journal of Computer Applications, 2016, 36(10): 2704-2709.
[7]	SUN Sanshan, WANG Shuai, FAN Zifu. Flow scheduling cost based congestion control routing algorithm for data center network on software defined network architecture [J]. Journal of Computer Applications, 2016, 36(7): 1784-1788.
[8]	CHEN Yixian WANG Yuan. Extended joint channel estimation in cooperative multi-cell OFDM systems [J]. Journal of Computer Applications, 2013, 33(05): 1225-1229.
[9]	DU Yao GUO Tao CHEN Junjie. Fleet elastic load balancing mechanism in cloud environment [J]. Journal of Computer Applications, 2013, 33(03): 830-833.
[10]	LI Ming YANG Lei WU Yanling. Quality assurance mechanism based on wireless TCP cross-layer service in mobile Ad Hoc network [J]. Journal of Computer Applications, 2013, 33(01): 83-87.
[11]	YANG Xiao-qin ZHANG Li-fang CAO Qing-huang SUN Hai-yan LI Zhuo-qing. Routing algorithm based on link bandwidth utilization rate [J]. Journal of Computer Applications, 2012, 32(09): 2422-2425.
[12]	XU Zhi-hong LIU Jin-jun ZHAO Sheng-hui. Live migration model of virtual machine adapting to wide area network [J]. Journal of Computer Applications, 2012, 32(07): 1929-1931.
[13]	Fei FANG Yu-ming MAO Su-peng LENG Jian-bing MAO. Analysis of approximate algorithm about adaptative p-persistent slotted ALOHA [J]. Journal of Computer Applications, 2011, 31(04): 897-900.
[14]	. Domain Partition and Controller Placement Strategies for Large SDN [J]. , 0, (): 0-0.

Steiner tree heuristic algorithm based on weighted node

基于加权节点的Steiner树启发式算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics