An Optimal Algorithm for Layered Wheel Floorplan Designs




Bettayeb, Said

Journal Title

Journal ISSN

Volume Title


Journal Networks


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) time and O(n) space, where n is the number of layers in the floorplan. In the worst case, it takes O(2) time and O(2) 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.



Algorithm Best, worst and average case Optimization problem Mathematical optimization Time complexity Analysis of algorithms Polynomial Computation John D. Wiley Very-large-scale integration Scroll wheel


• An Optimal Algorithm for Layered Wheel Floorplan Designs, (with P. Kulasinghe), Journal Networks Vol. 34, 1999, pp. 67-72.