|
Mon, Dec.18, 2006 |
Tue, Dec.19, 2006 |
Wed, Dec. 20, 2006 |
|||
|
08:30-12:00 |
Registration |
08:30-12:00 |
Registration |
08:30-12:00 |
Registration |
|
09:00-09:40 |
Opening: Conference Chair |
08:45-09:20 |
Best Student Paper |
08:45-10:25 |
Session 6A: Algorithms Session 6B: Graphs |
|
09:40-10:40 |
Invited Talk: Kazuo Iwama |
09:20-09:55 |
Best Paper |
10:25-10:55 |
Coffee Break |
|
10:40-11:15 |
Coffee Break |
09:55-10:10 |
Coffee Break |
10:55-12:10 |
Session 7A: Approximation Session 7B: Graphs |
|
11:15-12:30 |
Session 1A: Algorithms Session 1B: Online |
10:10-11:10 |
Invited Talk: Tamal K. Dey |
 |
 |
|
 |
 |
11:10-11:30 |
Coffee Break |
 |
 |
|
 |
 |
11:30-12;00 |
Presentation from IBM |
 |
 |
|
12:30-13:45 |
Lunch |
12:00-13:20 |
Lunch |
12:10-13:20 |
Lunch |
|
13:45-15:25 |
Session 2A Approximation Session 2B: Graphs |
13:20-15:00 |
Session 4A: Algorithms Session 4B: Networks |
13:20-15:00 |
Session 8A: Optimization and Quantum Session 8B: Online |
|
15:25-15:55 |
Coffee Break |
15:00-15:30 |
Coffee Break |
15:00-15:30 |
Coffee Break |
|
15:55-18:00 |
Session 3A: Geometry Session 3B: Complexity |
15:30-17:35 |
Session 5A: Optimization and Biology Session 5B Graphs |
15:30-17:10 |
Session 9A: Geometry Session 9B: Distributed and Cryptography |
|
 |
 |
19:00-21:00 |
 |
 |
|
Â
|
 Monday, December 18, 2006  |
|
|
09:00-09:40 |
Opening: Conference Chair |
|
09:40-10:40 |
Invited Talk: "Stable Matching Problems" by Kazuo Iwama, Kyoto University, Japan |
|
10:40-11:15 |
Coffee Break |
|
11:15-12:30 |
Session 1A: Algorithms and Data Structures |
|
11:15-11:40 |
Tobias Lenz, "Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees" |
|
11:40-12:05 |
Shay Solomon and Yefim Dinitz, "Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules" |
|
12:05-12:30 |
Robert Schweller, Manan Sanghi and Ming-Yang Kao, "Flexible Word Design and Graph Labeling" |
|
11:15-12:30 |
Session 1B: Online Algorithms |
|
11:15-11:40 |
Wun-Tat Chan, Francis Chin, Deshi Ye, Yong Zhang and Hong Zhu, "Frequency Allocation Problem for Linear Cellular Networks" |
|
11:40-12:05 |
Takashi Horiyama, Kazuo Iwama and Jun Kawahara, "Finite-State Online Algorithms and Their Automated Competitive Analysis" |
|
12:05-12:30 |
Vinayaka Pandit and Rohit Khandekar, "Offline sorting buffers on Line" |
|
12:30-13:45 |
Lunch |
|
13:45-15:25 |
Session 2A: Approximation Algorithms |
|
13:45-14:10 |
Tatsuya Akutsu, Daiji Fukagawa and Atsuhiro Takasu, "Approximating Tree Edit Distance Through String Edit Distance" |
|
14:10-14:35 |
Kiyoko Aoki-Kinoshita, Minoru Kanehisa, Ming-Yang Kao, Xiang-Yang Li and Weizhao Wang, "A 6-Approximation Algorithm for Computing Smallest Common AoN-supertree With Application to the Reconstruction of Glycan Trees" |
|
14:35-15:00 |
Fabrizio Grandoni and Giuseppe Italiano, "Improved Approximation for Single-Sink Buy-at-Bulk" |
|
15:00-15:25 |
Takehiro Ito, Erik Demaine, Xiao Zhou and Takao Nishizeki, "Approximability of Partitioning Graphs with Supply and Demand" |
|
13:45-15:25 |
Session 2B: Graphs |
|
13:45-14:10 |
Akira Kamada, Kazuyuki Miura and Takao Nishizeki, "Convex Grid Drawings of Plane Graphs with Rectangular Contours" |
|
14:10-14:35 |
Divesh Aggarwal, Chandan Dubey and Shashank K. Mehta, "Algorithms on graphs with small dominating targets" |
|
14:35-15:00 |
Telikepalli Kavitha and Chintan Shah, "Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems" |
|
15:00-15:25 |
Sumit Ganguly and Barna Saha, "On Estimating Path Aggregates over Streaming Graphs" |
|
15:25-15:55 |
Coffee Break |
|
15:55-18:00 |
Session 3A: Computational Geometry |
|
15:55-16:20 |
Prosenjit Bose, Michiel Smid and Daming Xu, "Diamond Triangulations Contain Spanners of Bounded Degree" |
|
16:20-16-45 |
Sang Won Bae, Jae-Hoon Kim and Kyung-Yong Chwa, "Optimal Construction of the City Voronoi Diagram" |
|
16:45-17:10 |
Yusu Wang, "Relations between two common types of rectangular tilings" |
|
17:10-17:35 |
Xinwei Shi and Ho-lun Cheng, "Quality Tetrahedral Mesh Generation for Macromolecules" |
|
17:35-18:00 |
Khaled Elbassioni, Aleksei Fishkin and Rene Sitters, "On Approximating the TSP with intersecting Neighborhoods" |
|
15:55-18:00 |
Session 3B: Computational Complexity |
|
15:55-16:20 |
Venkatesan Guruswami, "On 2-Query Codeword Testing With Near-Perfect Completeness" |
|
16:20-16-45 |
VIkraman Arvind and Jacobo Toran, "The Complexity of Quasigroup Isomorphism and the Minimum Generating Set" |
|
16:45-17:10 |
Michael Krueger and Harald Hempel, "Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING are coNP-complete" |
|
17:10-17:35 |
Sylvain Guillemot, "Parameterized complexity of some problems on coincidence graphs" |
|
17:35-18:00 |
Kazuo Iwama, Hiroki Morizumi and Jun Tarui, "Negation-Limited Complexity of Parity and Inverters" |
|
 Tuesday, December 19, 2006  |
|
|
08:45-09:20 |
Best Student Paper: Serge Gaspers, Fedor Fomin and Saket Saurabh, "Branching and Treewidth Based Exact Algorithms" |
|
09:20-09:55 |
Best Paper: Erik Demaine, MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi, "Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction" |
|
09:55-10:10 |
Coffee Break |
|
10:10-11:00 |
Invited Talk: Delaunay "Meshing of Surfaces" by Prof. Tamal K. Dey, The Ohio State University, USA |
|
11:00-11:30 |
Coffee Break |
|
11:30-12:00 |
Presentation from IBM |
|
12:00-13:20 |
Lunch |
|
13:20-15:00 |
Session 4A: Algorithms and Data Structures |
|
13:20-13:45 |
Jussi Kujala and Tapio Elomaa, "Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance" |
|
13:45-14:10 |
Xiaodong Wu, "Efficient Algorithms for the Optimal-Ratio Region Detection Problems in Discrete Geometry with Applications" |
|
14:10-14:35 |
Hsiao-Fei Liu and Kun-Mao Chao, "On Locating Disjoint Segments with Maximum Sum of Densities" |
|
14:35-15:00 |
Amr Elmasry, Jyrki Katajainen and Claus Jensen, "Two-Tier Relaxed Heaps" |
|
13:20-15:00 |
Session 4B: Games and Networks |
|
13:20-13:45 |
Benjamin Doerr, Johannes Lengler and David Steurer, "The Interval Liar Game" |
|
13:45-14:10 |
Gennaro Cordasco and Luisa Gargano, "How Much Independent Should Individual Contacts be to Form a Small-World?" |
|
14:10-14:35 |
Ferdinando Cicalese, Fredrik Manne and Qin Xin, "Faster Centralized Communication in Radio Networks" |
|
14:35-15:00 |
Robert Elsaesser and Thomas Sauerwald, "On the Runtime and Robustness of Randomized Broadcasting" |
|
15:00-15:30 |
Coffee Break |
|
15:30-17:35 |
Session 5A: Combinatorial Optimization and Computational Biology |
|
15:30-15:55 |
Dirk Sudholt, "Local Search in Evolutionary Algorithms: the Impact of the Local Search Frequency" |
|
15:55-16:20 |
Martin Hoefer, "Non-cooperative Facility Location and Covering Games" |
|
16:20-16:45 |
Qiaosheng Shi, Binay Bhattacharya, Arie Tamir and Yuzhuang Hu, "Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees" |
|
16:45-17:10 |
George Tsaggouris and Christos Zaroliagis, "Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications" |
|
17:10-17:35 |
Costas Iliopoulos and M Sohel Rahman, "Algorithms for Computing Variants of the Longest Common Subsequence Problem" |
|
15:30-17:35 |
Session 5B: Graphs |
|
15:30-15:55 |
Amos Korman, David Peleg and Yoav Rodeh, "Constructing Labeling Schemes through Universal Matrices" |
|
15:55-16:20 |
Federico Mancini, Pinar Heggernes and Charis Papadopoulos, "Making arbitrary graphs transitively orientable: Minimal comparability completions" |
|
16:20-16:45 |
Henning Meyerhenke and Thomas Sauerwald, "Analyzing Disturbed Diffusion on Networks" |
|
16:45-17:10 |
Chunmei Liu and Yinglei Song, "Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs" |
|
17:10-17:35 |
VIkraman Arvind, Bireswar Das and Partha Mukhopadhyay, "On Isomorphism and Canonization of Tournaments and Hypertournaments" |
|
19:00-21:00 |
Conference Dinner |
|
 Wednesday, December 20, 2006  |
|
|
08:45-10:25 |
Session 6A: Algorithms and Data Structures |
|
08:45-09:10 |
Tien-Ching Lin and D. T. Lee, "Efficient Algorithm for the Sum Selection Problem and K Maximum Sums Problem" |
|
09:10-09:35 |
Tobias Friedrich and Benjamin Doerr, "Deterministic Random Walks on the Two-Dimensional Grid" |
|
09:35-10:00 |
Shirou Maruyama, Hiromitsu Miyagawa and Hiroshi Sakamoto, "Improving Time and Space Complexity for Compressed Pattern Matching" |
|
10:00-10:25 |
Yunhong Zhou, "Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems" |
|
08:45-10:25 |
Session 6B: Graphs |
|
08:45-09:10 |
Mikael Onsjoe and Osamu Watanabe, "A Simple Message Passing Algorithm for Graph Partition Problem" |
|
09:10-09:35 |
Karol Suchan and Ioan Todinca, "Minimal Interval Completion Through Graph Exploration" |
|
09:35-10:00 |
Josep Diaz, Fabrizio Grandoni and Alberto Marchetti-Spaccamela, "Balanced Cut Approximation in Random Geometric Graphs" |
|
10:00-10:25 |
Tzu-Chin Lin, Hung-I Yu and Biing-Feng Wang, "Improved Algorithms for the Minmax-Regret 1-Center Problem" |
|
10:25-10:55 |
Coffee Break |
|
10:55-12:10 |
Session 7A: Approximation Algorithms |
|
10:55-11:20 |
Danny Z. Chen, Rudolf Fleischer, Jian Li, Zhiyi Xie and Hong Zhu, "On approximating the maximum simple sharing problem" |
|
11:20-11:45 |
Lukasz Kowalik, "Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures" |
|
11:45-12:10 |
Mingen Lin, Yang Yang and Jinhui Xu, "Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems" |
|
10:55-12:10 |
Session 7B: Graphs |
|
10:55-11:20 |
Guido Proietti and Peter Widmayer, "Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii" |
|
11:20-11:45 |
Saswata Shannigrahi and Sudebkumar Prasant Pal, "Efficient Prufer-like coding and counting labelled hypertrees" |
|
11:45-12:10 |
Joachim Kneis, Daniel Moelle, Stefan Richter and Peter Rossmanith, "Intuitive Algorithms and t-Vertex Cove" |
|
12:10-13:20 |
Lunch |
|
13:20-15:00 |
Session 8A: Combinatorial Optimization and Quantum Computing |
|
13:20-13:45 |
Allan Scott, Ulrike Stege and Norbert Zeh, "Politician's Firefighting" |
|
13:45-14:10 |
Frank Neumann and Carsten Witt, "Runtime Analysis of a Simple Ant Colony Optimization Algorithm" |
|
14:10-14:35 |
Andris Ambainis, William Gasarch, Aravind Srinivasan and Andrey Utis, "Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems" |
|
14:35-15:00 |
Peter Hoyer, Mehdi Mhalla and Simon Perdrix, "Resources required for preparing graph states" |
|
13:20-15:00 |
Session 8B: Online Algorithms |
|
13:20-13:45 |
Stefan Ruhrup and Christian Schindelhauer, "Online Multi-Path Routing in a Maze" |
|
13:45-14:10 |
Weimin Ma and Ke Wang, "On the On-line k-Truck Problem with Benefit Maximization" |
|
14:10-14:35 |
Patrick Briest and Christian Gunia, "Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels" |
|
14:35-15:00 |
Mohamed Aly and John Augustine, "Online Packet Admission and Oblivious Routing in Sensor Networks" |
|
15:00-15:30 |
Coffee Break |
|
15:30-17:10 |
Session 9A: Computational Geometry |
|
15:30-15:55 |
Danny Z. Chen and Chao Wang, "Field Splitting Problems in Intensity-Modulated Radiation Therapy" |
|
15:55-16:20 |
Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Ewa Misiolek and Chao Wang, "Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy" |
|
16:20-16:45 |
Katarzyna Paluch, "New approximation algorithms for multidimensional rectangle tiling" |
|
16:45-17:10 |
Scott Dillard, Gunther Weber, Vijay Natarajan, Valerio Pascucci and Bernd Hamann, "Tessellation of Quadratic Elements" |
|
15:30-17:10 |
Session 9B: Distributed Computing and Cryptography |
|
15:30-15:55 |
Shantanu Das, Paola Flocchini, Amiya Nayak and Nicola Santoro, "Effective Elections for Anonymous Mobile Agents" |
|
15:55-16:20 |
Ralf Klasing, Euripides Markou and Andrzej Pelc, "Gathering Asynchronous Oblivious Mobile Robots in a Ring" |
|
16:20-16:45 |
Christian Hundt, Maciej Liskiewicz and Ulrich Woelfel, "Provably Secure Steganography and the Complexity of Sampling" |
Â
Â