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

作     者：周智 蒋承东 黄刘生 顾钧 

作者机构：中国科学技术大学计算机科学与技术系 国家高性能计算中心(合肥)安徽合肥230027 香港科学技术大学计算机科学系中国香港 

基　　金：国家重点基础研究发展规划(973)~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2003年第14卷第9期

页      码：1503-1514页

摘      要：在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树构造算法,其平均情况时间复杂度只有Q(t).

主 题 词：VLSI设计 连接图 最短路径 最小Steiner树 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13328/j.cnki.jos.2003.09.001

馆 藏 号：203321251...