Generating Tatami Coverings Efficiently

MaRDI QIDQ6249944zbMATH OpenFDO

Authors Alejandro Erickson, Frank Ruskey

Publication date 19 March 2014

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Polyominoes (05B50)

Abstract: We present two algorithms to list certain classes of monomino-domino coverings which conform to the emph{tatami} restriction; no four tiles meet. Our methods exploit structural features of tatami coverings in order to create the lists in $O(1)$ time per covering. This is faster than known methods for generating certain classes of matchings in bipartite graphs. We discuss tatami coverings of $nimesn$ grids with $n$ monominoes and $v$ vertical dominoes, as well as tatami coverings of a two-way infinitely-wide strip of constant height, subject to the constraint that they have a finite number of non-trivial structural "features". These two classes are representative of two differing structural characterisations of tatami coverings which may be adapted to count other classes of tatami coverings or locally restricted matchings, such as tatami coverings of rectangles.

This page was built for publication: Generating Tatami Coverings Efficiently

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