Geodesic
The complexity of generalized domino tilings
Igor Pak1 ; Jed Yang2
1Department of Mathematics UCLA Los Angeles, CA 90095, U.S.A.
2School of Mathematics University of Minnesota Minneapolis, MN 55455, U.S.A.
The electronic journal of combinatorics, Tome 20 (2013) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2554
Classification : 52C22, 05B45, 68Q17
Mots-clés : tilings, dominoes, complexity

Igor Pak  1   ; Jed Yang  2

1 Department of Mathematics UCLA Los Angeles, CA 90095, U.S.A.
2 School of Mathematics University of Minnesota Minneapolis, MN 55455, U.S.A. 
@article{10_37236_2554,
     author = {Igor Pak and Jed Yang},
     title = {The complexity of generalized domino tilings},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {4},
     doi = {10.37236/2554},
     zbl = {1295.52026},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2554/}
}
TY  - JOUR
AU  - Igor Pak
AU  - Jed Yang
TI  - The complexity of generalized domino tilings
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2554/
DO  - 10.37236/2554
ID  - 10_37236_2554
ER  - 
%0 Journal Article
%A Igor Pak
%A Jed Yang
%T The complexity of generalized domino tilings
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2554/
%R 10.37236/2554
%F 10_37236_2554
Igor Pak; Jed Yang. The complexity of generalized domino tilings. The electronic journal of combinatorics, Tome 20 (2013) no. 4. doi: 10.37236/2554

Cité par Sources :