On the exact complexity of polyomino packing

DOI10.4230/LIPICS.FUN.2018.9MaRDI QIDQ3305727zbMATH OpenOpenAlexFDO

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

Publication date 11 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.FUN.2018.9

zbMATH Keywords

exact complexityexponential time hypothesispolyomino packing

Mathematics Subject Classification ID

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

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

(7)

• On the exact complexity of polyomino packing
• Small polyomino packing
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• scientific article; zbMATH DE number 4057528 (Why is no real title available?)
• Packing polyominoes clumsily
• scientific article; zbMATH DE number 1122697 (Why is no real title available?)
• Games, Puzzles and Treewidth

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 Q3305727)