The Complexity of Generalized Domino Tilings

  • Igor Pak
  • Jed Yang
DOI: https://doi.org/10.37236/2554
Keywords: tilings, dominoes, complexity

Abstract

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.
Published
2013-10-28
How to Cite
Pak, I., & Yang, J. (2013). The Complexity of Generalized Domino Tilings. The Electronic Journal of Combinatorics, 20(4), P12. https://doi.org/10.37236/2554
Issue
Volume 20, Issue 4 (2013)
Article Number
P12