Optimum Partitioning of a Rectilinear Layout

Simple item page
dc.contributor.authorLiang-Ping KUen_US
dc.contributor.authorHon Wai LEONGen_US
dc.date.accessioned2004-10-21T14:28:52Zen_US
dc.date.accessioned2017-01-23T07:00:30Z
dc.date.available2004-10-21T14:28:52Zen_US
dc.date.available2017-01-23T07:00:30Z
dc.date.issued1995-02-01T00:00:00Zen_US
dc.description.abstractGiven a rectilinear layout consisting of $n$ non-overlapping rectangles, we consider the problem of decomposing the remaining {\em free space} into rectangular {\em free blocks}. This problem is studied in connection with two problems from VLSI design, namely, design rule checking (DRC) using the corner stitching data structure, and the channel creation phase of global routing of VLSI building block layouts. In DRC using corner stitching, the decomposition is done via vertical partitioning. Similarly, horizontal partitioning can also be used. However, if we allow a hybrid of vertical and horizontal partitioning, the number of free blocks can be further reduced. In this paper, we consider the {\em optimum partitioning problem} in which we are interested in finding a decomposition that has the {\em minimum} number of free blocks. Given {\em any partition} of the free space, we first give a formula for counting the number of free blocks. The formula shows that the number of free blocks is determined by the number of {\em special} partition edges. We model the problem of finding an optimum partition as the problem of finding a maximum independent set in a bipartite graph. Finally, we give an $O( n ^ {2.5} ) $ algorithm for computing an optimum partition of any layout.en_US
dc.format.extent330279 bytesen_US
dc.format.extent842748 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/postscripten_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1381en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRC2/95en_US
dc.titleOptimum Partitioning of a Rectilinear Layouten_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
report.ps
Size:
823 KB
Format:
Postscript Files
Description:
Download
Thumbnail Image
Name:
report.pdf
Size:
322.54 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.52 KB
Format:
Plain Text
Description:
Download
Collections
Technical Reports