A fast algorithm for area minimization of slicing floorplans Academic Article

abstract

• The traditional algorithm for area minimization of slicing floorplans due to Stockmeyer has time and space complexity O(n2) in the worst case. For more than a decade, it has been considered the best possible. This paper presents a new algorithm of worst-case time and space complexity O(nlogn), where n is the total number of realizations for the basic blocks, regardless whether the slicing is balanced or not. We also show 7(?ilog n) is the lower bound on the time complexity of any area minimization algorithm. Therefore, the new algorithm not only finds the optimal realization, but also has the optimal running time. 1996 IEEE.

authors

• Shi, Weiping

published proceedings

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

author list (cited authors)

• Shi, W.

citation count

• 24

complete list of authors

• Shi, Weiping

publication date

• January 1996

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

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

Digital Object Identifier (DOI)

• 10.1109/43.552085

start page

• 1525

end page

• 1532

volume

• 15

issue

• 12

URL

• http://dx.doi.org/10.1109/43.552085