A Note on the Complexity of Stockmeyer's floorplan Optimization Technique

Ting Chi Wang, Martin Ding Fat Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review


Stockmeyer in Ref. 1 presented an optimal algorithm to solve the floorplan area optimization problem in polynomial time. Although his algorithm was designed only for slicing floorplans, the technique he used can be naturally extended to solve the problem for hierarchical floorplans. In this paper, we study the worst-case time complexity of Stockmeyer's technique to solve the floorplan area optimization problem for hierarchical floorplans of order 5. We show that Stockmeyer's technique inherently has exponential worst-case time complexity for this class of floorplans. Our proof is based on the fact that we can construct examples of hierarchical floorplans of order 5 such that the number of all non-redundant implementations for any of such floorplans is exponential in the total number of modules. We also observe that if the modules all have integer dimensions, the problem can be solved in pseudo-polynomial time by Stockmeyer's technique.
Original languageEnglish
Title of host publicationAlgorithmic Aspects of VLSI Layout
EditorsMajid Sarrafzadeh , D. T. Lee
PublisherWorld Scientific
Number of pages12
ISBN (Electronic)9789814502856, 9789812794468
ISBN (Print)9789810214883, 981021488X
Publication statusPublished - Nov 1993

Publication series

NameLecture Notes Series on Computing
ISSN (Print)1793-1223

User-Defined Keywords

  • Floorplan design
  • floorplan area optimization
  • Stockmeyer's technique
  • slicing floorplans
  • hierarchical floorplans


Dive into the research topics of 'A Note on the Complexity of Stockmeyer's floorplan Optimization Technique'. Together they form a unique fingerprint.

Cite this