Tiling with bars and satisfaction of Boolean formulas

DOI10.1006/EUJC.1996.0042MaRDI QIDQ1922876zbMATH OpenOpenAlexFDO

Authors Eric Rémila

Publication date 23 March 1997

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/eujc.1996.0042

zbMATH Keywords

3-satisfiabilitybarslinear algorithmNP-hardnessplane figuresplane tessellationpolyominoessquarestiling

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Combinatorial aspects of tessellation and tiling problems (05B45) Polyominoes (05B50)

Review text

The paper considers plane figures made up from finitely many squares of the plane tessellation by unit squares. It is proved that the problem of tiling such a figure with horizontal or vertical bars of length 2 or 3 can be reduced in linear time (in the area of the figure) to the logic problem 3-SAT (3-satisfiability). In particular, this gives a linear algorithm which, given a figure \(F\), either exhibits a tiling of \(F\) or indicates that such a tiling cannot exist.

Recommendations

• Tiling with bars and satisfaction of boolean formulas
• Tiling figures of the plane with two bars
• Hard tiling problems with simple tiles
• Tiling a simply connected figure with bars of length 2 or 3

Cited in

(7)

• Tiling a simply connected figure with bars of length 2 or 3
• Tiling figures of the plane with two bars
• Almost tiling of the Boolean lattice with copies of a poset
• Complexity of tiling a polygon with trominoes or bars
• scientific article; zbMATH DE number 1421183 (Why is no real title available?)
• Tiling with bars and satisfaction of boolean formulas
• scientific article; zbMATH DE number 3894472 (Why is no real title available?)

This page was built for publication: Tiling with bars and satisfaction of Boolean formulas

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