Tiling with bars and satisfaction of Boolean formulas
type: Item
instance of: scholarly article
title: Tiling with bars and satisfaction of Boolean formulas
zbMATH Open document ID: 0863.05024
author: Eric Rémila
published in: European Journal of Combinatorics
publication date: 1997-03-23T00:00:00Z
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.
Mathematics Subject Classification ID: 05B45
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 05B50
zbMATH DE Number: 930073
zbMATH Keywords: polyominoes
zbMATH Keywords: NP-hardness
zbMATH Keywords: 3-satisfiability
zbMATH Keywords: plane figures
zbMATH Keywords: squares
zbMATH Keywords: plane tessellation
zbMATH Keywords: tiling
zbMATH Keywords: bars
zbMATH Keywords: linear algorithm
reviewed by: Egon Schulte
MaRDI profile type: Publication
full work available at URL: eujc.1996.0042
OpenAlex ID: W1989161236
DOI: 10.1006/EUJC.1996.0042
description: scientific article; zbMATH DE number 930073