New algorithm for solving degree constrained minimum spanning tree problem

doi:10.3778/j.issn.1002-8331.2010.36.011

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (36): 40-42.DOI: 10.3778/j.issn.1002-8331.2010.36.011

• 研究、探讨 • Previous Articles Next Articles

New algorithm for solving degree constrained minimum spanning tree problem

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³

1.Department of Mathematics，Baoji College of Arts & Science，Baoji，Shaanxi 721013，China
2.School of Science，Xidian University，Xi’an 710071，China
3.General Armament Department Military Representative Office in Tianshui Region，Baoji，Shaanxi 721006，China

Received:2009-08-19 Revised:2009-10-09 Online:2010-12-21 Published:2010-12-21
Contact: SUN Xiao-jun

求解度约束最小生成树问题的新算法

孙小军¹，刘三阳²，王志强³

1.宝鸡文理学院数学系，陕西宝鸡 721013
2.西安电子科技大学理学院，西安 710071
3.总装备部驻天水地区军事代表室，陕西宝鸡 721006

通讯作者: 孙小军

Abstract

Abstract: Regarding the characteristics of degree-constrained minimum spanning tree problem in network design and combinatorial optimization，a new algorithm for the the k-degree minimum spanning tree on a designated point is presented on the base of the k minimum spanning tree’s algorithm.This new algorithm is supposed to change the minimum spanning tree in the optimal and operable way，and gradually make the degree of the designated point to be closer to the i-degree minimum spanning tree and finally reach the k-degree minimum spanning tree in network G.The correctness of this algorithm is proved by the given specific steps.Finally，the simulation and a practical transportation example turn out that the new algorithm is effective in the degree constrained minimum spanning tree problem.

Key words: degree, degree-constrain, minimum spanning tree, the k minimum spanning tree, the k-degree minimum spanning tree

摘要： 针对网络设计和组合优化中的度约束最小生成树问题，基于第k最小生成树的求解算法，提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换，逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树，最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤，并证明了算法的正确性。最后通过仿真结果和一个运输实例，表明了该算法在解决度约束最小生成树问题中的有效性。

关键词: 度, 度约束, 最小生成树, 第k最小生成树, 最小k度生成树

CLC Number:

TP301.6

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³. New algorithm for solving degree constrained minimum spanning tree problem[J]. Computer Engineering and Applications, 2010, 46(36): 40-42.

孙小军¹，刘三阳²，王志强³. 求解度约束最小生成树问题的新算法[J]. 计算机工程与应用, 2010, 46(36): 40-42.

[1]	ZHANG Qishan, CHEN Lulu. Slope One Algorithm Based on Grey Correlational Analysis by Method of Degree of Balance and Approach [J]. Computer Engineering and Applications, 2021, 57(9): 96-102.
[2]	JIANG Bin, LIANG Xiao’an, ZHANG Liang, GAO Yangjun. Evidence Combination Method Based on Improved Modified Weight [J]. Computer Engineering and Applications, 2021, 57(24): 100-106.
[3]	ZHONG Lei, WANG Yingming. Dynamic Group Decision Making Method of Interval 2-Tuple Linguistic Information Considering Psychological Behavior [J]. Computer Engineering and Applications, 2021, 57(2): 127-133.
[4]	TONG Wenlin, CHEN Dewang, HUANG Yunhu, LYU Yisheng. Fuzzy System Optimization Method Based on Simulated Annealing and Rule Reduction [J]. Computer Engineering and Applications, 2021, 57(16): 142-150.
[5]	CHE Minshi, NIE Chunyan, YANG Chengjin, RUAN Xinlei, FAN Rujun. Research on Correlation Between Physiological Signal and Emotion Based on Grey Relational Method [J]. Computer Engineering and Applications, 2021, 57(11): 168-172.
[6]	YAN Jiazhan, CHEN Hua, LI Yang. Improved Fuzzy C-Means Clustering Validity Index [J]. Computer Engineering and Applications, 2020, 56(9): 156-161.
[7]	SONG Juan. Pythagorean Decision-Making Model Considering Fusion Algorithms and Cross-Entropy [J]. Computer Engineering and Applications, 2020, 56(5): 74-79.
[8]	ZHAO Liang, ZHU Zhengyu. Overlapping Community Discovery Algorithm with K-Kernel Iteration Factor [J]. Computer Engineering and Applications, 2020, 56(3): 61-67.
[9]	BAO Shun, XU Xin, XIAO Jian, ZHOU Ligang. Pythagorean Hesitant Fuzzy Grey Correlation Multi-attribute Decision Making Method Based on Prospect Theory [J]. Computer Engineering and Applications, 2020, 56(18): 119-123.
[10]	CHEN Panpan, LIN Menglei. Attributes Reduction of Single Valued Neutrosophic Decision Information System Based on Inclusion Degree [J]. Computer Engineering and Applications, 2020, 56(12): 175-181.
[11]	QIN Xu, YANG Wenzhong, WANG Xueying, MA Guoxiang, WANG Qingpeng. Multi-source Topic Fusion Model Based on Co-occurrence Relation [J]. Computer Engineering and Applications, 2020, 56(10): 157-162.
[12]	DENG Yu, CHEN Guihui, LI Zhongbing, ZHANG Junhao, KANG Yuxin, XIA Xuhong. Non-local Stereo Matching Algorithm Based on Image Color and Edge [J]. Computer Engineering and Applications, 2020, 56(10): 199-204.
[13]	SONG Sensen1, JIA Zhenhong1, YANG Jie2, Nikola KASABOV3. Image Segmentation Algorithm of Minimum Spanning Tree Combined with Ostu Threshold Method [J]. Computer Engineering and Applications, 2019, 55(9): 178-183.
[14]	QIN Xiaoyan. Quasi-Truth Degree of First-Order Formula After Using Generalization Rule [J]. Computer Engineering and Applications, 2019, 55(6): 39-41.
[15]	WU Huihui1, GAO Shuping1, PENG Hongming2, ZHAO Yi1. Adaptive Fuzzy [C]-Means Clustering Data Fusion Algorithm [J]. Computer Engineering and Applications, 2019, 55(5): 26-35.

New algorithm for solving degree constrained minimum spanning tree problem

求解度约束最小生成树问题的新算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics