Room A | Room B | |
9:00 – 9:10 | Opening | |
9:10 – 10:10 | Invited Talk Chair: Seokhee Hong Testuo Asano. |
|
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 |