The complexity of generalized domino tilings

Igor Pak, Jed Yang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Tiling planar regions with dominoes is a classical problem in which 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.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume20
Issue number4
DOIs
StatePublished - Oct 28 2013

Keywords

  • Complexity
  • Dominoes
  • Tilings

Fingerprint Dive into the research topics of 'The complexity of generalized domino tilings'. Together they form a unique fingerprint.

Cite this