On the exact complexity of polyomino packing

DOI10.1016/j.tcs.2020.05.025zbMath1453.68092MaRDI QIDQ2196557

Hans L. Bodlaender, Tom C. van der Zanden

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 hypothesis; exact complexity; polyomino packing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05B40: Combinatorial aspects of packing and covering

05B50: Polyominoes