基于整数线性规划和分支定界构建MRST的快速算法研究

• 作者: 刘阳兴
• 来源期刊: 南开大学学报（自然科学版）
• 学科: 工学
• 关键词: 集成电路布线 Steiner树 MRST 整数线性规划 计算几何
• 年，卷（期）: 2012,（4）
• 页码范围: 58-62
• 页数: 5页
• 分类号: TN47
• 语种: 中文

摘要

最小直角斯坦纳树(MRST)的构建是集成电路布线、组合优化以及计算几何中的一个基础问题.针对MRST问题的高计算复杂度,通过结合MRST的解空间特点,巧妙建立该问题的整数线性规划模型;并利用计算机几何形状分析及分支定界算法来减少搜索空间,从而提高构建MRST算法的搜索效率.实验结果表明,算法不仅可以准确地构建出MRST,而且具有很高的计算效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘阳兴		2	8	1.0	2.0