【摘要】 <正> 一、引言 在通道布线时,目前较多采用的方法是水平和垂直走向分层,通过引线孔来完成互连。在工艺中,水平采用铝线,垂直采用多晶硅的方法用得很普遍,在这种情况下,两种材料的阻值相差很大。一种比较可行的方法是采用river-ronte的方法,找出线网,集中一些比较重要的线网将其布在金属尾上,然后在两层上布完余下的线网。由此,就有一个平面性问题以及线网集中最大平面可布的子集。对于后者,本文提出了O(N~2)的算法。更多还原

【Abstract】 This paper presents a new algorithm to find a maximum planar subset for a set of nets in a channel with O(N2) time, where N is the number of net.更多还原