December 17 (Wed)

Room A Room B
9:00 – 10:00 Invited Talk
Chair: Takuro Fukunaga

Robert E. Tarjan.
Reachability Problems on Directed Graphs

10:00 – 10:30 Coffee Break
Computational Geometry II
Chair: Sandor Fekete
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)
Chair: Christoph Buchheim
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