The complexity of generalized domino tilings (Q396923)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of generalized domino tilings |
scientific article |
Statements
The complexity of generalized domino tilings (English)
0 references
14 August 2014
0 references
Summary: Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial. We prove a variety of hardness results (both NP- and \#P-completeness) for different generalizations of dominoes in three and higher dimensions.
0 references
tilings
0 references
dominoes
0 references
complexity
0 references
0 references
