Hard Tiling Problems with Simple Tiles
| dc.creator | Moore, Cristopher | |
| dc.creator | Robson, John Michael | |
| dc.date | 2000-03-06 | |
| dc.date.accessioned | 2026-07-07T04:34:13Z | |
| dc.date.available | 2026-07-07T04:34:13Z | |
| dc.description | It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice. | |
| dc.identifier | https://arxiv.org/abs/math/0003039 | |
| dc.identifier | http://arxiv.org/abs/math/0003039 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/58817 | |
| dc.subject | Combinatorics | |
| dc.title | Hard Tiling Problems with Simple Tiles | |
| dc.type | text |