17. ISAAC 2006: Kolkata, India

Invited Talks

• Kazuo Iwama:
  Stable Matching Problems. 1
  
• Tamal K. Dey:
  Delaunay Meshing of Surfaces. 2
  

Best Paper 2006

• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi:
  Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction. 3-15
  

Best Student Paper 2006

• Fedor V. Fomin, Serge Gaspers, Saket Saurabh:
  Branching and Treewidth Based Exact Algorithms. 16-25
  

Algorithms and Data Structures

• Tobias Lenz:
  Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees. 26-35
  
• Yefim Dinitz, Shay Solomon:
  Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules. 36-47
  
• Ming-Yang Kao, Manan Sanghi, Robert T. Schweller:
  Flexible Word Design and Graph Labeling. 48-60
  

Online Algorithms

• Joseph Wun-Tat Chan, Francis Y. L. Chin, Deshi Ye, Yong Zhang, Hong Zhu:
  Frequency Allocation Problems for Linear Cellular Networks. 61-70
  
• Takashi Horiyama, Kazuo Iwama, Jun Kawahara:
  Finite-State Online Algorithms and Their Automated Competitive Analysis. 71-80
  
• Rohit Khandekar, Vinayaka Pandit:
  Offline Sorting Buffers on Line. 81-89
  

Approximation Algorithms

• Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu:
  Approximating Tree Edit Distance Through String Edit Distance. 90-99
  
• Kiyoko F. Aoki-Kinoshita, Minoru Kanehisa, Ming-Yang Kao, Xiang-Yang Li, Weizhao Wang:
  A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees. 100-110
  
• Fabrizio Grandoni, Giuseppe F. Italiano:
  Improved Approximation for Single-Sink Buy-at-Bulk. 111-120
  
• Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki:
  Approximability of Partitioning Graphs with Supply and Demand. 121-130
  

Graphs

• Akira Kamada, Kazuyuki Miura, Takao Nishizeki:
  Convex Grid Drawings of Plane Graphs with Rectangular Contours. 131-140
  
• Divesh Aggarwal, Chandan K. Dubey, Shashank K. Mehta:
  Algorithms on Graphs with Small Dominating Targets. 141-152
  
• Telikepalli Kavitha, Chintan D. Shah:
  Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems. 153-162
  
• Sumit Ganguly, Barna Saha:
  On Estimating Path Aggregates over Streaming Graphs. 163-172
  

Computational Geometry

• Prosenjit Bose, Michiel H. M. Smid, Daming Xu:
  Diamond Triangulations Contain Spanners of Bounded Degree. 173-182
  
• Sang Won Bae, Jae-Hoon Kim, Kyung-Yong Chwa:
  Optimal Construction of the City Voronoi Diagram. 183-192
  
• Yusu Wang:
  Relations Between Two Common Types of Rectangular Tilings. 193-202
  
• Ho-Lun Cheng, Xinwei Shi:
  Quality Tetrahedral Mesh Generation for Macromolecules. 203-212
  
• Khaled M. Elbassioni, Aleksei V. Fishkin, René Sitters:
  On Approximating the TSP with Intersecting Neighborhoods. 213-222
  

Computational Complexity

• Kazuo Iwama, Hiroki Morizumi, Jun Tarui:
  Negation-Limited Complexity of Parity and Inverters. 223-232
  
• Vikraman Arvind, Jacobo Torán:
  The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem. 233-242
  
• Michael Krüger, Harald Hempel:
  Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete. 243-252
  
• Sylvain Guillemot:
  Parameterized Problems on Coincidence Graphs. 253-266
  
• Venkatesan Guruswami:
  On 2-Query Codeword Testing with Near-Perfect Completeness. 267-276
  

Algorithms and Data Structures

• Jussi Kujala, Tapio Elomaa:
  Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance. 277-288
  
• Xiaodong Wu:
  Efficient Algorithms for the Optimal-Ratio Region Detection Problems in Discrete Geometry with Applications. 289-299
  
• Hsiao-Fei Liu, Kun-Mao Chao:
  On Locating Disjoint Segments with Maximum Sum of Densities. 300-307
  
• Amr Elmasry, Claus Jensen, Jyrki Katajainen:
  Two-Tier Relaxed Heaps. 308-317
  

Games and Networks

• Benjamin Doerr, Johannes Lengler, David Steurer:
  The Interval Liar Game. 318-327
  
• Gennaro Cordasco, Luisa Gargano:
  How Much Independent Should Individual Contacts Be to Form a Small-World? 328-338
  
• Ferdinando Cicalese, Fredrik Manne, Qin Xin:
  Faster Centralized Communication in Radio Networks. 339-348
  
• Robert Elsässer, Thomas Sauerwald:
  On the Runtime and Robustness of Randomized Broadcasting. 349-358
  

Combinatorial Optimization and Computational Biology

• Dirk Sudholt:
  Local Search in Evolutionary Algorithms: The Impact of the Local Search Frequency. 359-368
  
• Martin Hoefer:
  Non-cooperative Facility Location and Covering Games. 369-378
  
• Binay K. Bhattacharya, Yuzhuang Hu, Qiaosheng Shi, Arie Tamir:
  Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees. 379-388
  
• George Tsaggouris, Christos D. Zaroliagis:
  Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications. 389-398
  
• M. Sohel Rahman, Costas S. Iliopoulos:
  Algorithms for Computing Variants of the Longest Common Subsequence Problem. 399-408
  

Graphs

• Amos Korman, David Peleg, Yoav Rodeh:
  Constructing Labeling Schemes Through Universal Matrices. 409-418
  
• Pinar Heggernes, Federico Mancini, Charis Papadopoulos:
  Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions. 419-428
  
• Henning Meyerhenke, Thomas Sauerwald:
  Analyzing Disturbed Diffusion on Networks. 429-438
  
• Chunmei Liu, Yinglei Song:
  Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs. 439-448
  
• Vikraman Arvind, Bireswar Das, Partha Mukhopadhyay:
  On Isomorphism and Canonization of Tournaments and Hypertournaments. 449-459
  

Algorithms and Data Structures

• Tien-Ching Lin, D. T. Lee:
  Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem. 460-473
  
• Benjamin Doerr, Tobias Friedrich:
  Deterministic Random Walks on the Two-Dimensional Grid. 474-483
  
• Shirou Maruyama, Hiromitsu Miyagawa, Hiroshi Sakamoto:
  Improving Time and Space Complexity for Compressed Pattern Matching. 484-493
  
• Yunhong Zhou:
  Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems. 494-506
  

Graphs

• Mikael Onsjö, Osamu Watanabe:
  A Simple Message Passing Algorithm for Graph Partitioning Problems. 507-516
  
• Karol Suchan, Ioan Todinca:
  Minimal Interval Completion Through Graph Exploration. 517-526
  
• Josep Díaz, Fabrizio Grandoni, Alberto Marchetti-Spaccamela:
  Balanced Cut Approximation in Random Geometric Graphs. 527-536
  
• Tzu-Chin Lin, Hung-I Yu, Biing-Feng Wang:
  Improved Algorithms for the Minmax-Regret 1-Center Problem. 537-546
  

Approximation Algorithms

• Danny Z. Chen, Rudolf Fleischer, Jian Li, Zhiyi Xie, Hong Zhu:
  On Approximating the Maximum Simple Sharing Problem. 547-556
  
• Lukasz Kowalik:
  Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures. 557-566
  
• Mingen Lin, Yang Yang, Jinhui Xu:
  Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems. 567-577
  

Graphs

• Guido Proietti, Peter Widmayer:
  Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii. 578-587
  
• Saswata Shannigrahi, Sudebkumar Prasant Pal:
  Efficient Prüfer-Like Coding and Counting Labelled Hypertrees. 588-597
  
• Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith:
  Intuitive Algorithms and t-Vertex Cover. 598-607
  

Combinatorial Optimization and Quantum Computing

• Allan E. Scott, Ulrike Stege, Norbert Zeh:
  Politician's Firefighting. 608-617
  
• Frank Neumann, Carsten Witt:
  Runtime Analysis of a Simple Ant Colony Optimization Algorithm. 618-627
  
• Andris Ambainis, William I. Gasarch, Aravind Srinivasan, Andrey Utis:
  Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems. 628-637
  
• Peter Høyer, Mehdi Mhalla, Simon Perdrix:
  Resources Required for Preparing Graph States. 638-649
  

Online Algorithms

• Stefan Rührup, Christian Schindelhauer:
  Online Multi-path Routing in a Maze. 650-659
  
• Weimin Ma, Ke Wang:
  On the On-Line k-Truck Problem with Benefit Maximization. 660-669
  
• Patrick Briest, Christian Gunia:
  Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels. 670-679
  
• Mohamed Aly, John Augustine:
  Online Packet Admission and Oblivious Routing in Sensor Networks. 680-689
  

Computational Geometry

• Danny Z. Chen, Chao Wang:
  Field Splitting Problems in Intensity-Modulated Radiation Therapy. 690-700
  
• Danny Z. Chen, Xiaobo Sharon Hu, Shuang Luan, Ewa Misiolek, Chao Wang:
  Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy. 701-711
  
• Katarzyna E. Paluch:
  A New Approximation Algorithm for Multidimensional Rectangle Tiling. 712-721
  
• Scott E. Dillard, Vijay Natarajan, Gunther H. Weber, Valerio Pascucci, Bernd Hamann:
  Tessellation of Quadratic Elements. 722-731
  

Distributed Computing and Cryptography

• Shantanu Das, Paola Flocchini, Amiya Nayak, Nicola Santoro:
  Effective Elections for Anonymous Mobile Agents. 732-743
  
• Ralf Klasing, Euripides Markou, Andrzej Pelc:
  Gathering Asynchronous Oblivious Mobile Robots in a Ring. 744-753
  
• Christian Hundt, Maciej Liskiewicz, Ulrich Wölfel:
  Provably Secure Steganography and the Complexity of Sampling. 754-763