度、直径约束最小生成树问题及其算法  

Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm

作　　者：石磊[1] 冯祖针[1] 杨建强[1] 

机构地区：[1]红河学院数学学院,云南蒙自661100

出　　处：《云南民族大学学报（自然科学版）》2012年第4期295-297,共3页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：国家自然科学基金(11161020);红河学院硕博基金(10BSS136)

摘　　要：提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.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 0 （mn）. The algorithm was proved to be effective through analysis and experiments.

关 键 词：最小生成树 启发式算法 度约束 直径约束 

分 类 号：O157.6[理学—数学]