摘要
提出了一种基于计算几何学的面向两端线网的布线算法。对于给定的布线平面，该算法首先根据障碍情况构造了包含最短路径信息的强连接图，然后引入绕障碍长度作为参数，以决定搜索走向，算法保证能找到最短布线路径，并使其时空复杂度得到了极大的改善。
A new algorithm for two terminal net routing is presented,which is based on computational geometry.For a given routing plane,a strong connection graph with shortest path information is constructed as a parameter to select the right search direction.The algorithm will find out the shortest routing path only if it exists,and its time and space complexities have been significantly improved.
出处
《微电子学》
CAS
CSCD
北大核心
1999年第1期25-29,共5页
Microelectronics
基金
国家"九五"重点科技攻关项目资助
关键词
布线算法
最短路径
连接图
计算机辅助设计
Routing algorithm,Shortest path,Connection graph,Computer aided design
