Hard Tiling Problems with Simple Tiles

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.

Keywords

Combinatorics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/58817

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0003039
 http://arxiv.org/abs/math/0003039

Collections

arXiv