通道中线网最大平面可布子集的算法

摘要

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