The complexity of generalized domino tilings (Q396923): Difference between revisions

Summary: 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.

0 references

zbMATH Keywords

tilings

0 references

dominoes

0 references

complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Tiling figures of the plane with two bars

0 references

The undecidability of the domino problem

0 references

Filling Boxes with Bricks

0 references

Domino tiling in planar graphs with regular and bipartite dual. (Pavage par des dominos dans des graphes planaires de dual régulier et biparti)

0 references

Approximating the permanent of graphs with large factors

0 references

Planarity, Determinants, Permanents, and (Unique) Matchings

0 references

Q4521549

0 references

Statistical Mechanics of Dimers on a Plane Lattice

0 references

On generalized matching problems

0 references

Q4660723

0 references

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

0 references

The statistics of dimers on a lattice

0 references

Q4228435

0 references

Approximating the number of monomer-dimer coverings of a lattice.

0 references

Q4832435

0 references

Q3395507

0 references

Hard tiling problems with simple tiles

0 references

Tile invariants: New horizons.

0 references

Tiling simply connected regions with rectangles

0 references

Undecidability and nonperiodicity for tilings of the plane

0 references

The complexity of satisfiability problems

0 references

Q5491020

0 references

Conway's Tiling Groups

0 references

The Complexity of Counting in Sparse, Regular, and Planar Graphs

0 references

The Complexity of Enumeration and Reliability Problems

0 references

Identifiers

zbMATH Open document ID

1295.52026

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:396923

@@ Property / cites work @@
+Tiling figures of the plane with two bars
@@ Property / cites work: Tiling figures of the plane with two bars / rank @@
+Normal rank
@@ Property / cites work @@
+The undecidability of the domino problem
@@ Property / cites work: The undecidability of the domino problem / rank @@
+Normal rank
@@ Property / cites work @@
+Filling Boxes with Bricks
@@ Property / cites work: Filling Boxes with Bricks / rank @@
+Normal rank
@@ Property / cites work @@
+Domino tiling in planar graphs with regular and bipartite dual. (Pavage par des dominos dans des graphes planaires de dual régulier et biparti)
+Normal rank
@@ Property / cites work @@
+Approximating the permanent of graphs with large factors
+Normal rank
@@ Property / cites work @@
+Planarity, Determinants, Permanents, and (Unique) Matchings
+Normal rank
@@ Property / cites work @@
+Q4521549
@@ Property / cites work: Q4521549 / rank @@
+Normal rank
@@ Property / cites work @@
+Statistical Mechanics of Dimers on a Plane Lattice
+Normal rank
@@ Property / cites work @@
+On generalized matching problems
@@ Property / cites work: On generalized matching problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4660723
@@ Property / cites work: Q4660723 / rank @@
+Normal rank
@@ Property / cites work @@
+A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
+Normal rank
@@ Property / cites work @@
+The statistics of dimers on a lattice
@@ Property / cites work: The statistics of dimers on a lattice / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228435
@@ Property / cites work: Q4228435 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the number of monomer-dimer coverings of a lattice.
+Normal rank
@@ Property / cites work @@
+Q4832435
@@ Property / cites work: Q4832435 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3395507
@@ Property / cites work: Q3395507 / rank @@
+Normal rank
@@ Property / cites work @@
+Hard tiling problems with simple tiles
@@ Property / cites work: Hard tiling problems with simple tiles / rank @@
+Normal rank
@@ Property / cites work @@
+Tile invariants: New horizons.
@@ Property / cites work: Tile invariants: New horizons. / rank @@
+Normal rank
@@ Property / cites work @@
+Tiling simply connected regions with rectangles
@@ Property / cites work: Tiling simply connected regions with rectangles / rank @@
+Normal rank
@@ Property / cites work @@
+Undecidability and nonperiodicity for tilings of the plane
+Normal rank
@@ Property / cites work @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q5491020
@@ Property / cites work: Q5491020 / rank @@
+Normal rank
@@ Property / cites work @@
+Conway's Tiling Groups
@@ Property / cites work: Conway's Tiling Groups / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Counting in Sparse, Regular, and Planar Graphs
+Normal rank
@@ Property / cites work @@
+The Complexity of Enumeration and Reliability Problems
+Normal rank