On the exact complexity of polyomino packing

DOI10.1016/J.TCS.2020.05.025MaRDI QIDQ2196557zbMATH OpenOpenAlexFDO

Authors Tom C. van der Zanden, Hans L. Bodlaender

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8800/

zbMATH Keywords

exponential time hypothesisexact complexitypolyomino packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50)

Recommendations

• On the exact complexity of polyomino packing
• Small polyomino packing
• Rectangle packing with additional restrictions
• Complexity of tiling a polygon with trominoes or bars
• An algorithm for deciding if a polyomino tiles the plane

Cites work

• A Procedure for Improving the Upper Bound for the Number of n-Ominoes
• Games, puzzles, and computation
• Improved lower bounds for graph embedding problems
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• On the complexity of \(k\)-SAT
• Small polyomino packing
• Subexponential time algorithms for embedding \(H\)-minor free graphs
• Which problems have strongly exponential complexity?

Cited in

(8)

• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• On the decomposability of homogeneous binary planar configurations with respect to a given exact polyomino
• scientific article; zbMATH DE number 1122697 (Why is no real title available?)
• On the exact complexity of polyomino packing
• scientific article; zbMATH DE number 4057528 (Why is no real title available?)
• Small polyomino packing
• Packing polyominoes clumsily
• Complexity results for the horizontal bar packing problem

This page was built for publication: On the exact complexity of polyomino packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196557)