Hard and easy instances of L-tromino tilings
DOI10.1016/j.tcs.2020.02.025zbMath1433.68476OpenAlexW2763985444MaRDI QIDQ5919532
Marcos Villagra, Carlos F. Gaona, Fabricio Mendoza, Javier T. Akagi, Manjil Pratim Saikia
Publication date: 6 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://orca.cf.ac.uk/129923/1/paper_22.pdf
NP-completenessclaw-free graphsAztec diamondtrominopolyomino tilingsAztec rectangleefficient tilings
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Polyominoes (05B50)
Related Items (1)
Cites Work
- Unnamed Item
- Alternating sign matrices and descending plane partitions
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Alternating-sign matrices and domino tilings. I
- Tiling with polyominoes and combinatorial group theory
- Enumeration of domino tilings of an Aztec rectangle with boundary defects
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- Complexity of tiling a polygon with trominoes or bars
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Hard and easy instances of L-tromino tilings
- Hard tiling problems with simple tiles
This page was built for publication: Hard and easy instances of L-tromino tilings