Area minimization for hierarchical floorplans Academic Article

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.

authors

• Shi, Weiping

published proceedings

• IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

author list (cited authors)

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

complete list of authors

• Pan, P||Shi, W||Liu, CL

publication date

• December 1994

published in

• IEEE Transactions on Computer - Aided Design of Integrated Circuits and Systems  Journal

start page

• 436

end page

• 440