Area minimization for hierarchical floorplans Academic Article uri icon

abstract

  • Two results are presented in this paper. First we settle the open problem on the complexity of the area minimization problem for hierarchical floorplans by showing it to be N P-complete. We then present a pseudo-polynomial area minimization algorithm for hierarchical floorplans of order-5. The algorithm is based on a new algorithm for determining the set of nonredundant realizations of a wheel. The new algorithm for wheels has time cost O(k2log k) and space cost O(k2) if each of the (five) blocks in a wheel has at most k realizations - a reduction by a factor of k in both costs in comparison with previous algorithms. The area minimization algorithm was implemented. Our experimental results show that the algorithm is indeed very fast.

author list (cited authors)

  • Pan, P., Shi, W., & Liu, C. L.

publication date

  • December 1994