Manhattan空间有障碍的最短路径和3-Steiner树算法

• 作者: 周智 蒋承东 顾钧 黄刘生
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: VLSI设计 连接图 最短路径 最小Steiner树
• 年，卷（期）: 2003,（9）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1503-1514
• 页数: 12页
• 分类号: TP301
• 字数: 8333字
• 语种: 中文

摘要

在VLSI设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于2或大于2分别对应于Manhattan空间上有障碍时的最短路径问题和最小Steiner树问题,显然前者是后者的基础.连接图是研究最短路径问题的有效工具,已有的典型连接图包括基于轨迹的GC和GT以及基于自由区的GF和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法;分析了在各个连接图上构造3-Steiner树的算法,对于已有的GC上的3-Steiner算法,将其Steiner顶点的候选集合规模从O((e+p)2)降低到了O((t+p)2),其中e,t,p分别表示边数、障碍极边数和顶点数;设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有(θ)(t).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄刘生	中国科学技术大学计算机科学与技术系	134	1203	17.0	28.0
5	周智	中国科学技术大学计算机科学与技术系	13	69	5.0	8.0
9	蒋承东	中国科学技术大学计算机科学与技术系	1	14	1.0	1.0
13	顾钧	香港科学技术大学计算机科学系	5	43	4.0	5.0