DocumentCode
2250520
Title
A problem on rectangular floorplans
Author
Hakimi, S. Louis
Author_Institution
Dept. of Electr. Eng. & Comput. Sci., California Univ., Davis, CA, USA
fYear
1988
fDate
7-9 Jun 1988
Firstpage
1533
Abstract
Graph theory has been used in floorplanning for VLSI design. In particular, the problem of dissection of a rectangle into smaller rectangles with specified adjacencies has been well studied. In this problem, one has no control over the shapes (or aspect ratios) of any of the rectangles. The author studies the problem of packing rectangles with given areas and prescribed ranges for their aspect ratios into a rectangle of the least area. The problem is shown to be NP-complete. Some interesting special cases are shown to be solvable in polynomial time. Approximation algorithms are discussed for the general use
Keywords
VLSI; circuit layout; computational complexity; graph theory; mathematical programming; network topology; NP-complete; VLSI design; approximation algorithms; aspect ratios; circuit layout; graph theory; polynomial time; rectangular floorplans; Approximation algorithms; Bipartite graph; Graph theory; Polynomials; Routing; Shape control; Terminology; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location
Espoo
Type
conf
DOI
10.1109/ISCAS.1988.15222
Filename
15222
Link To Document