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

zbMATH Keywords

NP-completenessclaw-free graphsAztec diamondtrominopolyomino tilingsAztec rectangleefficient tilings

Mathematics Subject Classification ID

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)

On enumeration and entropy of ribbon tilings

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