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

• 作者: 冯祖针 杨建强 石磊 龙瑶
• 来源期刊: 沈阳大学学报
• 学科: 工学
• 关键词: 最小生成树问题 启发式算法 度约束 半径约束
• 年，卷（期）: 2012,（4）
• 所属期刊栏目: 信息与控制
• 页码范围: 63-65,73
• 页数: 4页
• 分类号: TP393.4
• 字数: 3206字
• 语种: 中文
• DOI: 10.3969/j.issn.1008-9225.2012.04.015

摘要

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