Complexity and approximability results for slicing floorplan designs

Deineko, Vladimir G. and Woeginger, Gerhard J. (2003) Complexity and approximability results for slicing floorplan designs. European Journal of Operational Research, 149 (3). pp. 533-539. ISSN 0377-2217

PDF
Restricted to UT campus only: Request a copy
288Kb

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.
Item Type:	Article
Copyright:	© 2003 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/75019
Official URL:	http://dx.doi.org/10.1016/S0377-2217(02)00527-1
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 213303