For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Notes on the One-Dimensional Compaction Problem of LSI Layouts Viewed from Network Flow Theory and Algorithms
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1986/10/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Mathematics, Combinatorics and Graph Theory
Full Text: PDF>>
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.