請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38252
標題: A Faster One-Dimensional Topological Compaction Algorithm
作者: H.F.S.Chen
D.T.Lee
關鍵字: Key words. VLSI, Homotopic compaction, Rubber-band equivalent
出版社: Springer Berlin Heidelberg
摘要: We consider the problem of one-dimensional topological compaction with jog insertions. By combining both geometric and graph-theoretic approaches we present a faster and simpler algorithm to improve over previous results. The compaction algorithm takes as input a sketch consisting of a set F of features and a set W of wires, and minimizes the horizontal width of the sketch while maintaining its routability. The algorithm consists of the following steps: constructing a horizontal constraint graph, computing all possible jog positions, computing the critical path, relocating the features, and reconstructing a new sketch homotopic to the input sketch, which is suitable for detailed routing. The algorithm runs in O(|F| ⋅ |W|) worst-case time and space, which is asymptotically optimal in the worst case. Experimental results are also presented.
URI: http://hdl.handle.net/11455/38252
ISSN: 1432-0541
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。