No easy puzzles: hardness results for jigsaw puzzles

DOI10.1016/J.TCS.2015.02.030MaRDI QIDQ2346997zbMATH OpenOpenAlexFDO

Authors Michael Brand

Publication date 26 May 2015

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.030

zbMATH Keywords

communication complexityjigsaw puzzleparsimonious testingsubgraph isomorphism

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Unique reconstruction threshold for random jigsaw puzzles
• Shotgun assembly of random jigsaw puzzles
• Automatic solution of jigsaw puzzles

Cites work

• A global approach to automatic solution of jigsaw puzzles
• An Algorithm for Subgraph Isomorphism
• Communication Complexity
• Decision procedures and expressiveness in the temporal logic of branching time
• Graph Isomorphism is in SPP
• Graph isomorphism is low for PP
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 168429 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1500534 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• On Representatives of Subsets
• Optimization for automated assembly of puzzles
• Polyominoes tiling by a genetic algorithm
• The complexity of theorem-proving procedures
• The Marriage Problem

Cited in

(6)

• Solving scramble squares puzzles with repetitions
• Automatic solution of jigsaw puzzles
• A global approach to automatic solution of jigsaw puzzles
• Shotgun assembly of random jigsaw puzzles
• Solving jigsaw puzzles by the graph connection Laplacian
• Unique reconstruction threshold for random jigsaw puzzles

This page was built for publication: No easy puzzles: hardness results for jigsaw puzzles

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