Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99369
Title: Optimum partitioning problem for rectilinear VLSI layout
Authors: Ku, L.-P. 
Leong, H.W. 
Keywords: Layout partitioning
VLSI
Issue Date: 1997
Source: Ku, L.-P.,Leong, H.W. (1997). Optimum partitioning problem for rectilinear VLSI layout. IEE Proceedings: Computers and Digital Techniques 144 (3) : 155-162. ScholarBank@NUS Repository.
Abstract: The authors consider the optimum partitioning problem defined as follows: given a rectilinear layout £consisting of n rectangles, it is desirable to partition (decompose) the remaining free space into rectangular free blocks using horizontal and/or vertical partition edges such that the number of free blocks is minimised. The authors give a new formula for counting the number of free blocks in any partition of a given layout. Based on the new formula, they show that the optimum partitioning problem reduces to the problem of finding a maximum independent vertex set (MIS) in a bipartite graph. They then give an O(/z2-5) optimum partitioning algorithm (OPA) for computing an optimum partition. This optimum partitioning algorithm can be used to improve the space and time complexities of many applications where space partitioning is encountered. One example is the corner stitching data structure used for design rule checker (DRC) in the layout system Magic. In the experiments, the space complexity of the corner stitching data structure can be improved by an average of 13% by using the proposed optimum partitioning. Other applications are also presented. © lEE, 1997.
Source Title: IEE Proceedings: Computers and Digital Techniques
URI: http://scholarbank.nus.edu.sg/handle/10635/99369
ISSN: 13502387
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

25
checked on Feb 22, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.