###
DOI:
Journal of Software:2003.14(9):1503-1514

Manhattan空间有障碍的最短路径和3-Steiner树算法
周智,蒋承东,黄刘生,顾钧
(中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;中国科学技术大学,计算机科学与技术系,安徽,合肥,230027;香港科学技术大学,计算机科学系,香港)
On Optimal Rectilinear Shortest Paths and 3-Steiner Tree Routing in Presence of Obstacles
ZHOU Zhi,JIANG Cheng-Dong,HUANG Liu-Sheng,GU Jun
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2880   Download 3966
Received:April 10, 2002    Revised:December 24, 2002
> 中文摘要: 在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).
Abstract:Finding networks with minimal cost to connect points is a key problem in VLSI design, which can be described as obstacle-avoiding shortest path and minimum Steiner tree problem according to whether the number of points is greater than 2. Connection graphs, such as track based on graphs GC and GT and free area based graphs GF and GG, are effective tools for the shortest path problem, which is the foundation of the Steiner tree problem. The contribution of this paper includes three points: The dynamic algorithms for querying the shortest path between two points on each connection graph are designed and analyzed for the first time; secondly, all algorithms for Steiner problem on each connection graph are analyzed; The number of candidate Steiner points is reduced from O((e+p)2) to O((t+p)2) in the 3-Steiner algorithm on GC, where e, t, p presents the number of edges, extreme edges of obstacles and terminals; An average Q(t) algorithm for 3-Steiner problem are designed on GG.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401 (国家重点基础研究发展规划(973) Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030401 (国家重点基础研究发展规划(973)
Foundation items:
Reference text:

周智,蒋承东,黄刘生,顾钧.Manhattan空间有障碍的最短路径和3-Steiner树算法.软件学报,2003,14(9):1503-1514

ZHOU Zhi,JIANG Cheng-Dong,HUANG Liu-Sheng,GU Jun.On Optimal Rectilinear Shortest Paths and 3-Steiner Tree Routing in Presence of Obstacles.Journal of Software,2003,14(9):1503-1514