A parallel algorithm for tiling problems
- 1 March 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 1 (1), 143-145
- https://doi.org/10.1109/72.80215
Abstract
A parallel algorithm for tiling with polyominoes is presented. The tiling problem is to pack polyominoes in a finite checkerboard. The algorithm using lxmxn processing elements requires O(1) time, where l is the number of different kinds of polyominoes on an mxn checkerboard. The algorithm can be used for placement of components or cells in a very large-scale integrated circuit (VLSI) chip, designing and compacting printed circuit boards, and solving a variety of two- or three-dimensional packing problems.Keywords
This publication has 7 references indexed in Scilit:
- Polyominoes which tile rectanglesJournal of Combinatorial Theory, Series A, 1989
- Combinatorial optimization with Gaussian machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Polyominoes on the infinite checkerboardJournal of Combinatorial Theory, Series A, 1980
- Mathematical GamesScientific American, 1975
- Tiling with sets of polyominoesJournal of Combinatorial Theory, 1970
- Packing a rectangle with congruent N-ominoesJournal of Combinatorial Theory, 1969
- Mathematical GamesScientific American, 1967