Science Journal of Applied Mathematics and Statistics

| Peer-Reviewed |

The Best Spanning Tree of Heterogeneous Node Weighted Graphs

Received: 16 January 2017    Accepted:     Published: 17 January 2017
Views:       Downloads:

Share This Article

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.

DOI 10.11648/j.sjams.20170501.12
Published in Science Journal of Applied Mathematics and Statistics (Volume 5, Issue 1, February 2017)
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), 2024. 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.
Author Information
  • Transportation Management College, Dalian Maritime University, Dalian, China

  • Department of Mathematics, Dalian Maritime University, Dalian, China

Cite This Article
  • 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://download.sciencepg.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

  • Sections