| Room A | Room B | |
| 9:00 – 10:00 | Invited Talk Chair: Takuro Fukunaga Robert E. Tarjan. |
|
| 10:00 – 10:30 | Coffee Break | |
| Computational Geometry II Chair: Sandor Fekete |
Network Chair: Hiro Ito | |
| 10:30 – 10:55 | Jonathan Backer and David Kirkpatrick. A Complete Approximation Algorithm for Shortest Bounded-Curvature Paths | Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcroft, Vahab Mirrokni and Shang-Hua Teng. On the Stability of Web Crawling and Web Search |
| 10:55 – 11:20 | Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler and Jun Luo. Detecting Commuting Patterns by Clustering Subtrajectories | Tobias Friedrich and Nils Hebbinghaus. Average Update Times for Fully-Dynamic All-Pairs Shortest Paths |
| 11:20 – 11:45 | Prosenjit Bose, Paz Carmi, Sébastien Collette and Michiel Smid. On the Stretch Factor of Convex Delaunay Graphs | Loukas Georgiadis. Computing Frequency Dominators and Related Problems |
| 11:45 – 12:10 | Hee-Kap Ahn, Peter Brass, Christian Knauer, Hyeon-Suk Na and Chan-Su Shin. Covering a Simple Polygon by Monotone Directions | Shantanu Das, Beat Gfeller and Peter Widmayer. Computing Best Swaps in Optimal Tree Spanners |
| 12:10– 14:00 | Lunch (Patio Restaurant) | |
| Optimization Chair: Christoph Buchheim |
Routing Chair: Andrew Goldberg | |
| 14:00– 14:25 | Hee-Kap Ahn and Sang Won Bae. Covering a Point Set by Two Disjoint Rectangles | Basile Couëtoux, Laurent Gourvès, Jérôme Monnot and Orestis A. Telelis. On Labeled Traveling Salesman Problems |
| 14:25– 14:50 | Christian Wulff-Nilsen. Computing the Maximum Detour of a Plane Graph in Subquadratic Time | Feodor F. Dragan and Martin Matamala. Navigating in a Graph by Aid of Its Spanning Tree |
| 14:50 – 15:15 | Harold N. Gabow and Shuxin Nie. Finding Long Paths, Cycles and Circuits | Binay Bhattacharya, Paz Carmi, Yuzhuang Hu and Qiaosheng Shi. Single Vehicle Scheduling Problem on Path/Tree/Cycle Networks with Release and Handling Times |
| 15:15 – 15:40 | Jun Luo and Christian Wulff-Nilsen. Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces | Daniel Delling and Giacomo Nannicini. Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks |
| 15:40 – 16:00 | Coffee Break | |
| Graph Algorithm II Chair: Giuseppe Liotta |
Complexity II Chair: Kazuyuki Amano | |
| 16:00 – 16:25 | Ryuhei Uehara. Bandwidth of Bipartite Permutation Graphs | Beate Bollig and Jochen Klump. New Results on the Most Significant Bit of Integer Multiplication |
| 16:25 – 16:50 | Andreas Brandstädt, Tilo Klembt, Vadim V. Lozin and Raffaele Mosca. Independent Sets of Maximum Weight in Apple-Free Graphs | Felix G. König and Marco E. Lübbecke. Sorting with Complete Networks of Stacks |
| 16:50 – 17:15 | Yasuko Matsui, Ryuhei Uehara and Takeaki
Uno.
Enumeration of Perfect Sequences of Chordal Graph |
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani and Shigeru Yamashita. Quantum Query Complexity of Boolean Functions with Small On-Sets |
| 17:15 – 17:40 | Vadim V. Lozin. From Tree-width to Clique-Width: Excluding a Unit Interval Graph | Ashley Montanaro, Harumichi Nishimura and Rudy Raymond. Unbounded-Error Quantum Query Complexity |
| 17:40 – 18:05 | Leizhen Cai, Elad Verbin and Lin Yang. Firefighting on Trees: (1-1/e)--Approximation, Fixed Parameter Tractability and a Subexponential Algorithm | Rūsiņš Freivalds. Super-exponential Size Advantage of Quantum Finite Automata with Mixed States |
| 18:05– 18:10 | Closing | |