On the exact complexity of polyomino packing
DOI10.1016/J.TCS.2020.05.025zbMATH Open1453.68092OpenAlexW3028659059MaRDI QIDQ2196557FDOQ2196557
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/
Recommendations
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)
Cites Work
- Which problems have strongly exponential complexity?
- On the complexity of \(k\)-SAT
- A Procedure for Improving the Upper Bound for the Number of n-Ominoes
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- Games, puzzles, and computation
- Small polyomino packing
- Subexponential time algorithms for embedding \(H\)-minor free graphs
- Improved lower bounds for graph embedding problems
Cited In (8)
- On the decomposability of homogeneous binary planar configurations with respect to a given exact polyomino
- On the exact complexity of polyomino packing
- Small polyomino packing
- Title not available (Why is that?)
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
- Complexity results for the horizontal bar packing problem
- Title not available (Why is that?)
- Packing polyominoes clumsily
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)
