The complexity of generalized domino tilings

Igor Pak; Jed Yang

doi:10.37236/2554

The complexity of generalized domino tilings

Igor Pak, Jed Yang

School of Mathematics

Research output: Contribution to journal › Article › peer-review

9 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 language	English (US)
Journal	Electronic Journal of Combinatorics
Volume	20
Issue number	4
DOIs	https://doi.org/10.37236/2554
State	Published - Oct 28 2013

Keywords

Complexity
Dominoes
Tilings

Publisher link

10.37236/2554

Find It

Find It at U of M Libraries

Cite this

@article{cb26294b286349e3ab018fa5c746dcdb,

title = "The complexity of generalized domino tilings",

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.",

keywords = "Complexity, Dominoes, Tilings",

author = "Igor Pak and Jed Yang",

year = "2013",

month = oct,

day = "28",

doi = "10.37236/2554",

language = "English (US)",

volume = "20",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - The complexity of generalized domino tilings

AU - Pak, Igor

AU - Yang, Jed

PY - 2013/10/28

Y1 - 2013/10/28

N2 - 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.

AB - 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.

KW - Complexity

KW - Dominoes

KW - Tilings

UR - http://www.scopus.com/inward/record.url?scp=84886822908&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84886822908&partnerID=8YFLogxK

U2 - 10.37236/2554

DO - 10.37236/2554

M3 - Article

AN - SCOPUS:84886822908

SN - 1077-8926

VL - 20

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

ER -

The complexity of generalized domino tilings

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this