• DocumentCode
    780325
  • Title

    An Ω(k2) lower bound for area optimization of spiral floorplans

  • Author

    Chen, Cheng-Hsi ; Tollis, Ioannis G.

  • Author_Institution
    Dept. of Comput. Sci., Texas Univ., Dallas, TX, USA
  • Volume
    15
  • Issue
    3
  • fYear
    1996
  • fDate
    3/1/1996 12:00:00 AM
  • Firstpage
    358
  • Lastpage
    360
  • Abstract
    Let F be a spiral floorplan where each of its five basic rectangles has k implementations. In this paper, we show that there can be as many as Ω(k2) useful implementations generated for F, in the worst case. This implies that the previously known O(k2 log k)-time algorithm is almost optimal
  • Keywords
    VLSI; circuit layout CAD; circuit optimisation; integrated circuit layout; VLSI layout; area optimization; lower bound; spiral floorplans; Area measurement; Circuits; Costs; Position measurement; Process design; Semiconductor device measurement; Shape; Spirals; Topology; Very large scale integration;
  • fLanguage
    English
  • Journal_Title
    Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0278-0070
  • Type

    jour

  • DOI
    10.1109/43.489106
  • Filename
    489106
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=780325