Notes on the One-Dimensional Compaction Problem of LSI Layouts Viewed from Network Flow Theory and Algorithms

Hiroshi IMAI  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E69   No.10   pp.1080-1083
Publication Date: 1986/10/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Mathematics, Combinatorics and Graph Theory
Keyword: 


Full Text: PDF>>
Buy this Article



Summary: 
The computational complexity of several problems in compacting LSI layouts are reviewed from the viewpoint of network flow theory and algorithms. It is shown that the general one-dimensional compaction problem of an LSI layout with n elements, such that the basic building blocks are rectilinear polygons connected by stretchable/shrinkable and movable wires, can be solved in O(n log n) time. Related problems of updating constraints on the layout are also considered.