| 度、半径约束最小生成树问题及其算法 |
| |
| 引用本文： | 成鹰. 度、半径约束最小生成树问题及其算法[J]. 沈阳大学学报：自然科学版, 2012, 24(4): 63-65,73 |
| |
| 作者姓名： | 成鹰 |
| |
| 作者单位： | 沈阳大学信息工程学院,辽宁沈阳,110044 |
| |
| 基金项目： | 云南省自然科学基金资助项目 |
| |
| 摘 要： | 提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.
|
| 关 键 词： | 最小生成树问题 启发式算法 度约束 半径约束 |
Degree-Constrained, Radius-Constrained Minimum Spanning Tree Problem and its Algorithm |
| |
| SHI Lei,FENG Zuzhen,YANG Jianqiang,LONG Yao. Degree-Constrained, Radius-Constrained Minimum Spanning Tree Problem and its Algorithm[J]. Journal of Shenyang University, 2012, 24(4): 63-65,73 |
| |
| Authors: | SHI Lei FENG Zuzhen YANG Jianqiang LONG Yao |
| |
| Affiliation: | (Department of Mathematics, Honghe University, Mengzi 661100, China) |
| |
| Abstract: | The degree-constrained, radius-constrained minimum spanning tree problem was put forward, and it was proved to be NP-complete. A mathematics programming model of the problem and a fast heuristic algorithm were proposed to solve the model. The time complexity of the algorithm was analyzed. The algorithm was proved to be effective by analysis and experiments. |
| |
| Keywords: | minimum spanning tree problem heuristic algorithm degree-constrainedradius-constrained |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
