近乎最佳的Manhattan型Steiner树近似算法

• 作者: 杨波 马军 马绍汉
• 来源期刊: 软件学报
• 学科: 数学
• 关键词: Steiner树 算法复杂性 组合优化 电路布线
• 年，卷（期）: 2000,（2）
• 页码范围: 260-264
• 页数: 5页
• 分类号: O157
• 字数: 3499字
• 语种: 中文

摘要

求解最佳的Manhattan型Steiner树问题(minimum rectilinear Steiner tree,简记为MRST问题)是在VLSI布线、网络通信中所遇到的组合优化问题,同时也是一个NP-难解问题.该文给出对该问题的O(n2)时间复杂性的近似算法.该算法在最坏情况下的近似比严格小于3/2.计算机实验结果表明,所求得的支撑树的平均费用与最佳算法的平均费用仅相差0.8%.该算法稍加修改,可应用到三维或多维的Manhattan空间对Steiner问题求解,且易于在并行与分布式环境下编程实现.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马绍汉	山东大学计算机科学系	39	302	10.0	15.0
2	杨波	山东大学计算机科学系	55	560	15.0	21.0
3	马军	山东大学计算机科学系	74	980	15.0	29.0