Graph theoretic technique to speed up floorplan area optimization

A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.