The complexity of generalized domino tilings

zbMATH Open1295.52026arXiv1305.2154MaRDI QIDQ396923FDOQ396923

Jed Yang, Igor Pak

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1305.2154

zbMATH Keywords

complexitytilingsdominoes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the number of monomer-dimer coverings of a lattice.
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Statistical Mechanics of Dimers on a Plane Lattice
• Conway's Tiling Groups
• The Complexity of Enumeration and Reliability Problems
• The complexity of satisfiability problems
• The undecidability of the domino problem
• Hard tiling problems with simple tiles
• The complexity of counting in sparse, regular, and planar graphs
• Tiling figures of the plane with two bars
• Domino tiling in planar graphs with regular and bipartite dual. (Pavage par des dominos dans des graphes planaires de dual régulier et biparti)
• Tile invariants: New horizons.
• Tiling simply connected regions with rectangles
• Undecidability and nonperiodicity for tilings of the plane
• On generalized matching problems
• Approximating the permanent of graphs with large factors
• Filling Boxes with Bricks
• Planarity, Determinants, Permanents, and (Unique) Matchings

Cited In (14)

• Flip invariance for domino tilings of three-dimensional regions with two floors
• Tiling with Squares and Packing Dominos in Polynomial Time
• Aspects of a multivariate complexity analysis for rectangle tiling
• Generalizing the divisibility property of rectangle domino tilings
• On the connectivity of spaces of three-dimensional domino tilings
• The lattice structure of the set of domino tilings of a polygon
• Rectangular tileability and complementary tileability are undecidable
• Tile complexity of approximate squares
• Computational complexity of counting coincidences
• Fast domino tileability
• Domino tilings and flips in dimensions 4 and higher
• On the shuffling algorithm for domino tilings
• A multiparameter analysis of domino tiling with an application to concurrent systems
• A note on a flip-connected class of generalized domino tilings of the box \([0,2]^n\)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Tiling with Squares and Packing Dominos in Polynomial Time 👍 👎
• The lattice structure of the set of domino tilings of a polygon 👍 👎
• Domino tilings and determinants 👍 👎
• The Tiling Problem Revisited (Extended Abstract) 👍 👎
• Algorithms and Computation 👍 👎
• Generalizing the divisibility property of rectangle domino tilings 👍 👎
• A note on the structure of spaces of domino tilings 👍 👎
• Reconstruction of domino tilings -- combinatorial and probabilistic questions 👍 👎

This page was built for publication: The complexity of generalized domino tilings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396923)