Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity

[Stephen Fulwider]

Hey everyone,

This Friday, Feb. 18th, I'll be covering a 2007 paper out of MIT by
Erik and Martin Demaine (some of you may be familiar with Erik Demaine
if you've ever watched any of the MIT CS courses through
OpenCourseWare).

The paper proves an equivalence between these types of puzzles and
shows that they are all NP-complete. We'll be covering their proofs of
equivalence and the how they show these to be NP-Complete.

You don't need to read the paper to attend, but in case you want to
look over it before or after the talk you can find it here:
http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBMQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.108.3689%26rep%3Drep1%26type%3Dpdf&rct=j&q=Jigsaw%20Puzzles%2C%20Edge%20Matching%2C%20and%20Polyomino%20Packing%3AConnections%20and%20Complexity&ei=0P5aTeWWIsuatwfnnvGQDA&usg=AFQjCNENNmAepQp67Z8-HHxaKUubz25yLw&sig2=QWBT35pzM6lYMyCrIoKiNw

See everyone on Friday!

Stephen