A note on domino shuffling

MaRDI QIDQ2500948zbMATH OpenFDO

Authors Élise Janvresse, Thierry de la Rue, Yvan Velenik

Publication date 30 August 2006

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

Full work available at URL https://eudml.org/doc/126453, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r30.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

algorithmAztec diamondsperfect matchingsplanar graphs

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Graph theory (including graph drawing) in computer science (68R10)

Review text

Summary: We present a variation of James Propp's generalized domino shuffling, which provides an efficient way to obtain perfect matchings of weighted Aztec diamonds. Our modification is specially tailored to deal with cases when some of the weights are zero. This allows us to tile efficiently a large class of planar graphs, by embedding them in a large enough Aztec diamond. We also give a sufficient condition on the size of the latter diamond for the algorithm to succeed.

Recommendations

• On the shuffling algorithm for domino tilings
• Generalized domino-shuffling.
• On the domino shuffle and matrix refactorizations
• On a problem in shuffling
• Domino shuffling on Novak half-hexagons and Aztec half-diamonds
• A generalization of the perfect shuffle
• scientific article; zbMATH DE number 5555045
• A note on the shuffle variant of Jeśmanowicz' conjecture
• The shuffle conjecture

Cited in

(11)

• Generalized domino-shuffling.
• Arctic curves of the 6V model with partial DWBC and double Aztec rectangles
• Tangent method for the arctic curve arising from freezing boundaries
• A heuristic approach to domino grid problem
• On λ-determinants and tiling problems
• Domino shuffling on Novak half-hexagons and Aztec half-diamonds
• Perfect t-embeddings of uniformly weighted Aztec diamonds and tower graphs
• Shuffling algorithm for coupled tilings of the Aztec diamond
• Local generation of tilings
• Boundary dents, the arctic circle and the arctic ellipse (with an appendix by Michael Larsen)
• On the shuffling algorithm for domino tilings

This page was built for publication: A note on domino shuffling

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