Program

Contributed Talks are 20 minutes long including Question/Answer Period.

Sunday, June 03

18:00-19:00/19:30: Welcome aperitif in San Servolo

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