ISAAC 2006 Final Program



December 17, 2006 (Sunday) 18:00-21:00 -- Registration and Welcome Dinner

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

Conference Dinner

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"