December 15 (Mon)

Room A Room B
9:00 – 9:10 Opening
9:10 – 10:10 Invited Talk
Chair: Seokhee Hong

Testuo Asano.
Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?

10:10 – 10:30 Coffee Break
Approximation Algorithm I
Chair: Christoph Buchheim
Online Algorithm
Chair: Hsu-Chun Yen
10:30 – 10:55 Zeyu Guo, He Sun and Hong Zhu. Greedy Construction of 2-Approximation Minimum Manhattan Network Sumit Ganguly. Data Stream Algorithms via Expander Graphs
10:55 – 11:20 Frank Kammer and Torsten Tholey. The Complexity of Minimum Convex Coloring Shuichi Miyazaki and Kazuya Okamoto. Improving the Competitive Ratio of the Online OVSF Code Assignment Problem
11:20 – 11:45 Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno. On the Complexity of Reconfiguration Problems Weiwei Wu, Minming Li and Enhong Chen. Optimal Key Tree Structure for Deleting Two or More Leaves
11:45 – 12:10 Christian Glaßer, Christian Reitwießner and Heinz Schmitz. Multiobjective Disk Cover Admits a PTAS Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt and Rodica Mihai. Comparing First-Fit and Next-Fit for Online Edge Coloring
12:10 – 14:00 Lunch (Patio Restaurant)
Data Structure and Algorithm
Chair: Lars Arge
Game Theory
Chair: Anastasios Viglas
14:00– 14:25 Gerth Stølting Brodal and Allan Grønlund Jørgensen. Selecting Sums in Arrays Yingchao Zhao, Wei Chen and Shang-Hua Teng. The Isolation Game: A Game of Distances
14:25– 14:50 Craig Dillabaugh, Meng He and Anil Maheshwari. Succinct and I/O Efficient Data Structures for Traversal in Trees Evangelos Bampas, Aris Pagourtzis, Giorgos Pierrakos and Katerina Potika. On a Non-Cooperative Model for Wavelength Assignment in Multifiber Optical Networks
14:50 – 15:15 Simon J. Puglisi and Andrew Turpin. Space-Time Tradeoffs for Longest-Common-Prefix Array Computation Shankar Kalyanaraman and Christopher Umans. The Complexity of Rationalizing Matchings
15:15 – 15:40 Daniel Raible and Henning Fernau. Power Domination in O*(1.7548^n) using Reference Search Trees Panagiota N. Panagopoulou and Paul G. Spirakis. A Game Theoretic Approach for Efficient Graph Coloring
15:40 – 16:00 Coffee Break
Graph Algorithm I
Chair: Kyung-Yong Chwa
Fixed Parameter Tractability
Chair: Giuseppe Liotta
16:00 – 16:25 [Best Paper Award] Takehiro Ito, Takeaki Uno, Xiao Zhou and Takao Nishizeki. Partitioning a Weighted Tree to Subtrees of Almost Uniform Size Joachim Kneis, Alexander Langer and Peter Rossmanith. A New Algorithm for Finding Trees with Many Leaves
16:25 – 16:50 Mingyu Xiao. An improved Divide-and-Conquer Algorithm for Finding All Minimum k-way Cuts Hans L. Bodlaender, Pinar Heggernes and Yngve Villanger. Faster Parameterized Algorithms for Minimum Fill-In
16:50 – 17:15 Michael Lampis, Georgia Kaouri and Valia Mitsou. On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond and Saket Saurabh. Graph Layout problems Parameterized by Vertex Cover
17:15 – 17:40 Maxim A. Babenko. An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem Hans L. Bodlaender, Eelko Penninkx and Richard B. Tan. A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
17:40 – 18:05 Yuta Harada, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita.

The Balanced Edge Cover Problem

Sounaka Mishra, Venkatesh Raman, Saket Saurabh and Somnath Sikdar. König Deletion Sets and Vertex Covers above the Matching Size