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 y-Tile Salvage Problem is: Given a map, find the maximum number of non-overlapping 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 NP-complete 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