The complexity of generalized domino tilings
From MaRDI portal
Publication:396923
zbMATH Open1295.52026arXiv1305.2154MaRDI QIDQ396923FDOQ396923
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
Recommendations
- Domino tilings and determinants
- Generalizing the divisibility property of rectangle domino tilings
- Algorithms and Computation
- Tiling with Squares and Packing Dominos in Polynomial Time
- Tilings, compositions, and generalizations
- The lattice structure of the set of domino tilings of a polygon
- The Tiling Problem Revisited (Extended Abstract)
- A note on the structure of spaces of domino tilings
- Reconstruction of domino tilings -- combinatorial and probabilistic questions
- On the tileability of polygons with colored dominoes
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
- 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
- A survey of Pfaffian orientations of graphs
- Conway's Tiling Groups
- Matching theory
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 (21)
- How to Tile by Dominoes the Boundary of a Polycube
- 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
- Title not available (Why is that?)
- Tiling a pyramidal polycube with dominoes
- The lattice structure of the set of domino tilings of a polygon
- Hard tiling problems with simple tiles
- Title not available (Why is that?)
- 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
- Algorithms and Computation
- On the shuffling algorithm for domino tilings
- Domino tatami covering is NP-complete
- 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\)
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)
