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

摘要

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.%提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.