Please enter verification code
The Best Spanning Tree of Heterogeneous Node Weighted Graphs
Science Journal of Applied Mathematics and Statistics
Volume 5, Issue 1, February 2017, Pages: 10-14
Received: Jan. 16, 2017; Published: Jan. 17, 2017
Views 4578      Downloads 128
Nana Wang, Transportation Management College, Dalian Maritime University, Dalian, China
Wei Liu, Department of Mathematics, Dalian Maritime University, Dalian, China
Article Tools
Follow on us
Minimum spanning tree theory has a wide application in many fields. But in many practical problems, we are often faced with the heterogeneous node weighted graph with both edge weight and node weight be considered. In this paper, we present the definition and the mathematical model of the best spanning tree, then raise an algorithm of the best spanning tree, finally, prove that the algorithm is effective in the best spanning tree problem through an application example.
Heterogeneous Node, The Best Spanning Tree, Algorithm, Reduced Graph
To cite this article
Nana Wang, Wei Liu, The Best Spanning Tree of Heterogeneous Node Weighted Graphs, Science Journal of Applied Mathematics and Statistics. Vol. 5, No. 1, 2017, pp. 10-14. doi: 10.11648/j.sjams.20170501.12
Kruskal J. On the Shortest Spanning Subtree of a Graph and the Traveling Sales Man Problem [J]. Proceedings of the AMS, 1956, 7 (1): 48-50.
PrimRC. Shortest Connection Networks and Some Generations [J]. Bell System Technical Journal, 1957, 36(6): 1389-1401.
Sollin M, LeTracede Canalisation. Programming, Games, and Transportation Networks [M]. New York, USA: John Wiley & Sons, Inc., 1965.
LONG Ya. Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule. Journal of Bijie University. 2007 (4): 108-111.
QIN Yanxin, WANG Yueguang. Algorithm of Finding all Minimum Spanning Trees by Breaking Loop. Journal of Air Force Radar Academy. 2006 (6), 135-137.
GUO Wenzhong, CHEN Guolong. An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree. PR&AI.2009 (8): 597-604.
Zhou Gengui, Gen M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree. European Journal of Operational Research. 1999, 114 (1): 141-152.
CHEN Guolong, GUO Wenzhong etc. An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree Problem. Journal of Software 2006. 364-370.
Kennedy. IEberhart R C. A Discrete Binary Version of the Particle Swarm Optimization Algorithm // Proc of IEEE International Conference on Systems Man and Cybemetics Orlando USA, 1997 (2) 4104-4109.
LI Feng, SHEN Huizhang, LI Li. The Panic Spreading on the Complicated Network of Heterogeneous Nodes Under Public Crisis. Mathematics in Practice and Theory. 2013 (1), 97-107.
R. H. Heiberger, Stock network stability in times of crisis, Physica A, 2014 (393): 376–381.
A. Q. Abbasi, W. A. Loun, Symbolic time series analysis of temporal gait dynamics, J. Signal Process. Syst. 2014(74): 417–422.
J. G. Brida, D. Matesanz, M. N. Seijas, Network analysis of returns and volume trading in stock markets: The Euro Stoxx case, Physica A. 2016 (444): 751–764.
SUN Xiaojun. Research Degree-Constrained Minimum Spanning Tree Problem Based on Prim Algorithm. Journal of Inner Mongolia Nortnal University. 2016, 45 (4), 445-448.
Torkestani J A. Degree Constrained Minimum Spanning Tree Problem: a Learning Automata Approach. Journal of Supercomputing, 2013, 64 (1): 226-249.
WANG Xi-li, LIN Hong-Shuai. Label Propagation Through Minimum Cost Path. Chinese Journal of Computers, 2016, 39 (7): 1407-1416.
Kim K H, Choi S. Label Propagation through minimax paths for scalable sctni-supervised learning, Pattern Pccognition letters, 2014, 45 (11): 17-25.
LIU Jian-Wei, Liu Yuan, LUO Xiong-Lin. Sctni-supervised Learning methods. Chinese Journal of Computers, 2015, 38 (8): 1592-1617.
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
Tel: (001)347-983-5186