
Accession Number : ADA119117
Title : Optimal Tile Salvage.
Descriptive Note : Technical rept.,
Corporate Author : PURDUE UNIV LAFAYETTE IN DEPT OF COMPUTER SCIENCES
Personal Author(s) : Berman,Francine ; Leighton,Frank Thomson ; Snyder,Lawrence
PDF Url : ADA119117
Report Date : May 1982
Pagination or Media Count : 24
Abstract : A map is a tiling of a finite region of the plane with unit squares such that some tiles have been removed. The optimal x x yTile Salvage Problem is: Given a map, find the maximum number of nonoverlapping x x y tiled rectangles. A polynomial time algorithm is given for the 1 x 2 case, i.e., adjacent pairs. It is shown that the problem is NPcomplete for the 2 x 2 case. A polynomial time algorithm is presented for finding 2 x 2 groups that is no worse than one half optimal. The problem is motivated by a technique for increasing the size of very large scale integrated (VLSI) circuit chips. (Author)
Descriptors : *Chips(Electronics), *Integrated circuits, *Wafers, Transistors, Polynomials, Packing Density, Algorithms, Defects(Materials), Configurations
Subject Categories : Electrical and Electronic Equipment
Distribution Statement : APPROVED FOR PUBLIC RELEASE