The complexity of generalized domino tilings
From MaRDI portal
Publication:396923
zbMath1295.52026arXiv1305.2154MaRDI QIDQ396923
Publication date: 14 August 2014
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.2154
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)
Related Items
On the connectivity of spaces of three-dimensional domino tilings, Fast domino tileability, Domino tilings and flips in dimensions 4 and higher, Rectangular tileability and complementary tileability are undecidable, Flip invariance for domino tilings of three-dimensional regions with two floors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generalized matching problems
- Approximating the permanent of graphs with large factors
- 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.
- Approximating the number of monomer-dimer coverings of a lattice.
- Tiling simply connected regions with rectangles
- Undecidability and nonperiodicity for tilings of the plane
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- The statistics of dimers on a lattice
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Conway's Tiling Groups
- Statistical Mechanics of Dimers on a Plane Lattice
- The Complexity of Enumeration and Reliability Problems
- The complexity of satisfiability problems
- Filling Boxes with Bricks
- The undecidability of the domino problem
- Planarity, Determinants, Permanents, and (Unique) Matchings
- Hard tiling problems with simple tiles
