An Optimal Algorithm for Layered Wheel Floorplan Designs

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