Program
Contributed Talks are 20 minutes long including Question/Answer Period.
Monday, June 04
09:00-09:50: Plenary Talk: Stability and Metastability of the Logit Dynamics of Strategic Games - Giuseppe Persiano
09:50-10:00 Break
10:00-11:20 Contributed Talks :
A new analysis of Best Fit bin packing - J. Sgall
Algorithms and Complexity of Generalized River Crossing Problems - Hiro Ito, Stefan Langerman and Yuichi Yoshida
Computing Maximum Hamiltonian Paths in Complete Graphs with Tree Metric - Bartosz Szreder and Wojciech Rytter
Conflict-free graph orientations with parity and degree constraints - Sarah Cannon, Mashhood Ishaque and Csaba Toth
11:20-11:40 Coffee Break
11:40-12:40 Contributed Talks
Scrabble is PSPACE-Complete - Michael Lampis, Valia Mitsou and Karolina Soltys
Solving Single-digit Sudoku Subproblems - David Eppstein
Solving Tantrix via Integer Programming - Fumika Kino and Yushi Uno
12:40-14:40 Lunch
14:40-16:00 Contributed Talks
Divorcing made easy - Kirk Pruhs and Gerhard J. Woeginger
Finding Good Coffee in Paris - Paola Flocchini, Matthew Kellett, Peter Mason and Nicola Santoro
Mad at edge crossings? Break the edges! - Till Bruckdorfer and Michael Kaufmann
Counting Perfect Matchings in Graphs of Degree 3 - Martin Fürer
16:00-16:20 Coffee Break
16:20-17:40 Contributed Talks
Gaming is a hard job, but someone has to do it! - Giovanni Viglietta
The Vulcan game of Kal-toh: Finding or making triconnected planar subgraphs - Terry Anderson and Therese Biedl
Grid Graphs with Diagonal Edges and the Complexity of Xmas Mazes - Markus Holzer and Sebastian Jakobi
Lean Programs, Branch Mispredictions, and Sorting - Amr Elmasry and Jyrki Katajainen
Tuesday, June 05
09:00-09:50: Plenary Talk
Art Galleries, k-modems, and k-convexity - Jorge Urrutia
09:50-10:00 Break
10:00-11:20 Contributed Talks
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns - Ellen Gethner, David Kirkpatrick and Nicholas Pippenger
Picture-Hanging Puzzles - Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest and Mihai Patrascu
Scienceography: the study of how science is written - Jinyun Yan, S Muthukrishnan and Graham Cormode
The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye - Michael Bender, Ritwik Bose, Rezaul Chowdhury and Samuel McCauley
11:20-11:40 Coffee Break
11:40-12:40 Contributed Talks
Hardness of Mastermind - Giovanni Viglietta
Hitori Number - Akira Suzuki, Kei Uchizawa and Takeaki Uno
Making life easier for firefighters - Fedor V. Fomin, Pinar Heggernes and Erik Jan Van Leeuwen
12:40-14:40 Lunch
14:40-16:00 Contributed Talks
On Computer Integrated Rationalized Crossword Puzzle Manufacturing - Jakob Engel, Markus Holzer, Oliver Ruepp and Frank Sehnke
Tron, a combinatorial game on abstract graphs - Tillmann Miltzow
To Satisfy Impatient Web surfers is Hard - Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric and Nicolas Nisse
On the Complexity of Rolling Block and Alice Mazes - Markus Holzer and Sebastian Jakobi
Excursion/Banquet
Wednesday, June 06
09:00-09:50: Plenary Talk : Distributed Algorithms by Forgetful Mobile Robots - Paola Flocchini
09:50-10:00 Break
10:00-11:20 Contributed Talks
Practical Algorithms for Generating a Random Ordering of the Elements of a Weighted Set - Kevin Lang
Scandinavian Thins over a Fat Top: on the Smallest One-Size-Fits-All Box - Esther Arkin, Alon Efrat, George Hart, Irina Kostitsyna, Alexander Kroeller, Joseph Mitchell and Valentin Polishchuk
Spanning trees and the complexity of flood-filling games - Kitty Meeks and Alex Scott
The Byzantine Brides Problem - Swan Dubois, Sébastien Tixeuil and Nini Zhu
11:20-11:40 Coffee Break
11:40-13:00 Contributed Talks
The Coolest Order of Binary Strings - Brett Stevens and Aaron Williams
The Multi-Interval Ulam-Rényi Game - Ferdinando Cicalese
Train Marshalling is Fixed Parameter Tractable - Leo Brueggeman, Michael Fellows, Rudolf Fleischer, Martin Lackner, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler and Frances Rosamond
Optimal Sensor Networks for Area Monitoring using Rotating and Beam Sensors - Stefan Dobrev, Lata Narayanan and Jaroslav Opatrny
13:00-15:00 Lunch