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
Item availability restricted. |
![]() |
PDF
- Accepted Post-Print Version
Restricted to Repository staff only until 21 February 2021 due to copyright restrictions. Download (491kB) |
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: | 10 Apr 2020 02:12 |
URI: | http://orca.cf.ac.uk/id/eprint/129922 |
Actions (repository staff only)
![]() |
Edit Item |