Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Hard and easy instances of L-tromino tilings

Akagi, Javier T., Gaona, Carlos F., Mendoza, Fabricio, Saikia, Manjil and Villagra, Marcos 2020. Hard and easy instances of L-tromino tilings. Theoretical Computer Science 815 , pp. 197-212. 10.1016/j.tcs.2020.02.025

[thumbnail of trominos.pdf]
Preview
PDF - Accepted Post-Print Version
Download (491kB) | Preview

Abstract

We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle and an Aztec diamond has an L-tromino tiling. Then, we study tilings of arbitrary regions where only rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contains certain so-called “forbidden polyominoes” as sub-regions, then there exists a polynomial time algorithm for deciding a tiling.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher: Elsevier
ISSN: 0304-3975
Date of First Compliant Deposit: 25 February 2020
Date of Acceptance: 17 February 2020
Last Modified: 07 Nov 2023 02:26
URI: https://orca.cardiff.ac.uk/id/eprint/129922

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics