Please use this identifier to cite or link to this item:
|Title:||Optimum partitioning problem for rectilinear VLSI layout||Authors:||Ku, L.-P.
|Issue Date:||1997||Citation:||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.
checked on Jan 26, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.