Premium
An optimal algorithm for layered wheel floorplan designs
Author(s) -
Kulasinghe Priyalal D.,
Bettayeb Saïd
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199908)34:1<67::aid-net7>3.0.co;2-w
Subject(s) - floorplan , algorithm , computer science , mathematical optimization , mathematics
In this paper, we present an efficient algorithm to solve the orientation optimization problem for a layered wheel floorplan. The strategy used is to generate all the nonredundant implementations for the floorplan. The computational complexities of the algorithm depend on the actual dimensions of the cells in the floorplan. In the best case, it takes O ( n 2 ) time and O ( n ) space, where n is the number of layers in the floorplan. In the worst case, it takes O (2 n ) time and O (2 n ) space. Furthermore, we prove that the time and space complexities for the worst case are optimal. A set of conditions is obtained to check whether the floorplan belongs to the worst case. Using these conditions, we show that even though the worst case is theoretically unavoidable it is not encountered in practical situations where the cell dimensions are bounded. © 1999 John Wiley & Sons, Inc. Networks 34: 67–72, 1999