| 度、直径约束最小生成树问题及其算法 |
| |
| 引用本文： | 石磊,冯祖针,杨建强. 度、直径约束最小生成树问题及其算法[J]. 云南民族大学学报(自然科学版), 2012, 21(4): 295-297 |
| |
| 作者姓名： | 石磊 冯祖针 杨建强 |
| |
| 作者单位： | 红河学院数学学院,云南蒙自,661100 |
| |
| 基金项目： | 国家自然科学基金，红河学院硕博基金 |
| |
| 摘 要： | 提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.
|
| 关 键 词： | 最小生成树 启发式算法 度约束 直径约束 |
Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm |
| |
| SHI Lei , FENG Zu-zhen , YANG Jian-qiang. Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm[J]. Journal of Yunnan Nationalities University:Natural Sciences Edition, 2012, 21(4): 295-297 |
| |
| Authors: | SHI Lei FENG Zu-zhen YANG Jian-qiang |
| |
| Affiliation: | (Department of Mathematics,Honghe University,Mengzi 661100,China) |
| |
| Abstract: | The degree-constrained and diameter-constrained minimum spanning tree problem was discussed,which proved to be NP-Complete.A mathematical programming model of the problem was proposed.A heuristic algorithm was proposed to solve this problem,whose time complexity was O(mn).The algorithm was proved to be effective through analysis and experiments. |
| |
| Keywords: | minimum spanning tree heuristic algorithm degree-constrained diameter-constrained |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
