The Best Spanning Tree of Heterogeneous Node Weighted Graphs

Nana Wang; Wei Liu

doi:doi:10.11648/j.sjams.20170501.12

| Peer-Reviewed

The Best Spanning Tree of Heterogeneous Node Weighted Graphs

Nana Wang, Wei Liu

Published in Science Journal of Applied Mathematics and Statistics (Volume 5, Issue 1)

Received: 16 January 2017 Published: 17 January 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

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.

Published in	Science Journal of Applied Mathematics and Statistics (Volume 5, Issue 1)
DOI	10.11648/j.sjams.20170501.12
Page(s)	10-14
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2017. Published by Science Publishing Group

Keywords

Heterogeneous Node, The Best Spanning Tree, Algorithm, Reduced Graph

References

[1]	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.
[2]	PrimRC. Shortest Connection Networks and Some Generations [J]. Bell System Technical Journal, 1957, 36(6): 1389-1401.
[3]	Sollin M, LeTracede Canalisation. Programming, Games, and Transportation Networks [M]. New York, USA: John Wiley & Sons, Inc., 1965.
[4]	LONG Ya. Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule. Journal of Bijie University. 2007 (4): 108-111.
[5]	QIN Yanxin, WANG Yueguang. Algorithm of Finding all Minimum Spanning Trees by Breaking Loop. Journal of Air Force Radar Academy. 2006 (6), 135-137.
[6]	GUO Wenzhong, CHEN Guolong. An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree. PR&AI.2009 (8): 597-604.
[7]	Zhou Gengui, Gen M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree. European Journal of Operational Research. 1999, 114 (1): 141-152.
[8]	CHEN Guolong, GUO Wenzhong etc. An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree Problem. Journal of Software 2006. 364-370.
[9]	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.
[10]	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.
[11]	R. H. Heiberger, Stock network stability in times of crisis, Physica A, 2014 (393): 376–381.
[12]	A. Q. Abbasi, W. A. Loun, Symbolic time series analysis of temporal gait dynamics, J. Signal Process. Syst. 2014(74): 417–422.
[13]	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.
[14]	SUN Xiaojun. Research Degree-Constrained Minimum Spanning Tree Problem Based on Prim Algorithm. Journal of Inner Mongolia Nortnal University. 2016, 45 (4), 445-448.
[15]	Torkestani J A. Degree Constrained Minimum Spanning Tree Problem: a Learning Automata Approach. Journal of Supercomputing, 2013, 64 (1): 226-249.
[16]	WANG Xi-li, LIN Hong-Shuai. Label Propagation Through Minimum Cost Path. Chinese Journal of Computers, 2016, 39 (7): 1407-1416.
[17]	Kim K H, Choi S. Label Propagation through minimax paths for scalable sctni-supervised learning, Pattern Pccognition letters, 2014, 45 (11): 17-25.
[18]	LIU Jian-Wei, Liu Yuan, LUO Xiong-Lin. Sctni-supervised Learning methods. Chinese Journal of Computers, 2015, 38 (8): 1592-1617.

Cite This Article

Plain Text BibTeX RIS

APA Style

Nana Wang, Wei Liu. (2017). The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Science Journal of Applied Mathematics and Statistics, 5(1), 10-14. https://doi.org/10.11648/j.sjams.20170501.12

Copy | Download

ACS Style

Nana Wang; Wei Liu. The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Sci. J. Appl. Math. Stat. 2017, 5(1), 10-14. doi: 10.11648/j.sjams.20170501.12

Copy | Download

AMA Style

Nana Wang, Wei Liu. The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Sci J Appl Math Stat. 2017;5(1):10-14. doi: 10.11648/j.sjams.20170501.12

Copy | Download

@article{10.11648/j.sjams.20170501.12,
  author = {Nana Wang and Wei Liu},
  title = {The Best Spanning Tree of Heterogeneous Node Weighted Graphs},
  journal = {Science Journal of Applied Mathematics and Statistics},
  volume = {5},
  number = {1},
  pages = {10-14},
  doi = {10.11648/j.sjams.20170501.12},
  url = {https://doi.org/10.11648/j.sjams.20170501.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.sjams.20170501.12},
  abstract = {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.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - The Best Spanning Tree of Heterogeneous Node Weighted Graphs
AU  - Nana Wang
AU  - Wei Liu
Y1  - 2017/01/17
PY  - 2017
N1  - https://doi.org/10.11648/j.sjams.20170501.12
DO  - 10.11648/j.sjams.20170501.12
T2  - Science Journal of Applied Mathematics and Statistics
JF  - Science Journal of Applied Mathematics and Statistics
JO  - Science Journal of Applied Mathematics and Statistics
SP  - 10
EP  - 14
PB  - Science Publishing Group
SN  - 2376-9513
UR  - https://doi.org/10.11648/j.sjams.20170501.12
AB  - 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.
VL  - 5
IS  - 1
ER  -

Copy | Download

Author Information

Nana Wang

Transportation Management College, Dalian Maritime University, Dalian, China
Wei Liu

Department of Mathematics, Dalian Maritime University, Dalian, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Nana Wang, Wei Liu. (2017). The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Science Journal of Applied Mathematics and Statistics, 5(1), 10-14. https://doi.org/10.11648/j.sjams.20170501.12

Copy | Download

ACS Style

Nana Wang; Wei Liu. The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Sci. J. Appl. Math. Stat. 2017, 5(1), 10-14. doi: 10.11648/j.sjams.20170501.12

Copy | Download

AMA Style

Nana Wang, Wei Liu. The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Sci J Appl Math Stat. 2017;5(1):10-14. doi: 10.11648/j.sjams.20170501.12

Copy | Download

@article{10.11648/j.sjams.20170501.12,
  author = {Nana Wang and Wei Liu},
  title = {The Best Spanning Tree of Heterogeneous Node Weighted Graphs},
  journal = {Science Journal of Applied Mathematics and Statistics},
  volume = {5},
  number = {1},
  pages = {10-14},
  doi = {10.11648/j.sjams.20170501.12},
  url = {https://doi.org/10.11648/j.sjams.20170501.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.sjams.20170501.12},
  abstract = {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.},
 year = {2017}
}

Copy | Download

TY  - JOUR
T1  - The Best Spanning Tree of Heterogeneous Node Weighted Graphs
AU  - Nana Wang
AU  - Wei Liu
Y1  - 2017/01/17
PY  - 2017
N1  - https://doi.org/10.11648/j.sjams.20170501.12
DO  - 10.11648/j.sjams.20170501.12
T2  - Science Journal of Applied Mathematics and Statistics
JF  - Science Journal of Applied Mathematics and Statistics
JO  - Science Journal of Applied Mathematics and Statistics
SP  - 10
EP  - 14
PB  - Science Publishing Group
SN  - 2376-9513
UR  - https://doi.org/10.11648/j.sjams.20170501.12
AB  - 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.
VL  - 5
IS  - 1
ER  -

Copy | Download