Purdue e-Pubs (Purdue University System) · 1981 · 10 citations · 2 references
Open access
EngineeringComputer EngineeringComputer ScienceAlgorithmsCircuit TheorySystem-on-chip DesignCircuit ComplexityCombinatorial OptimizationVery-large-scale Integration LayoutPolynomial Time ComplexityPolynomial-time AlgorithmsTiling ProblemsTiling Theory
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)
2
Planar Formulae and Their Uses
David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations