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

Hiroshi IMAI  

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

Full Text: PDF>>
Buy this Article

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.