The Library
Complexity and approximability results for slicing floorplan designs
Tools
UNSPECIFIED (2003) Complexity and approximability results for slicing floorplan designs. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 149 (3). pp. 533-539. doi:10.1016/S0377-2217(02)00527-1 ISSN 0377-2217.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/S0377-2217(02)00527-1
Abstract
The first stage in hierarchical approaches to floorplan design determines certain topological relations between the positions of indivisible cells on a VLSI chip. Various optimizations are then performed on this initial layout to minimize certain cost measures such as the chip area. We consider optimization problems in fixing the orientations of the cells and simultaneously fixing the directions of the cuts that are specified by a given slicing tree; the goal is to minimize the area of the chip.
We prove that these problems are NP-hard in the ordinary sense, and we describe a pseudo-polynomial time algorithm for them. We also present fully polynomial time approximation schemes for these problems. (C) 2002 Elsevier Science B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management | ||||
Journal or Publication Title: | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0377-2217 | ||||
Official Date: | 16 September 2003 | ||||
Dates: |
|
||||
Volume: | 149 | ||||
Number: | 3 | ||||
Number of Pages: | 7 | ||||
Page Range: | pp. 533-539 | ||||
DOI: | 10.1016/S0377-2217(02)00527-1 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |