17. ISAAC 2006: Kolkata, India

Tetsuo Asano (Ed.): Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings. Lecture Notes in Computer Science 4288 Springer 2006, ISBN 3-540-49694-7 BibTeX

Invited Talks

Kazuo Iwama:
Stable Matching Problems. 1
Electronic Edition (link) BibTeX
Tamal K. Dey:
Delaunay Meshing of Surfaces. 2
Electronic Edition (link) BibTeX

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
Electronic Edition (link) BibTeX

Best Student Paper 2006

Fedor V. Fomin, Serge Gaspers, Saket Saurabh:
Branching and Treewidth Based Exact Algorithms. 16-25
Electronic Edition (link) BibTeX

Algorithms and Data Structures

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

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
Electronic Edition (link) BibTeX
Takashi Horiyama, Kazuo Iwama, Jun Kawahara:
Finite-State Online Algorithms and Their Automated Competitive Analysis. 71-80
Electronic Edition (link) BibTeX
Rohit Khandekar, Vinayaka Pandit:
Offline Sorting Buffers on Line. 81-89
Electronic Edition (link) BibTeX

Approximation Algorithms

Tatsuya Akutsu, Daiji Fukagawa, Atsuhiro Takasu:
Approximating Tree Edit Distance Through String Edit Distance. 90-99
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
Fabrizio Grandoni, Giuseppe F. Italiano:
Improved Approximation for Single-Sink Buy-at-Bulk. 111-120
Electronic Edition (link) BibTeX
Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki:
Approximability of Partitioning Graphs with Supply and Demand. 121-130
Electronic Edition (link) BibTeX

Graphs

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

Computational Geometry

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

Computational Complexity

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

Algorithms and Data Structures

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

Games and Networks

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

Combinatorial Optimization and Computational Biology

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

Graphs

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

Algorithms and Data Structures

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

Graphs

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

Approximation Algorithms

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

Graphs

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

Combinatorial Optimization and Quantum Computing

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

Online Algorithms

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

Computational Geometry

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

Distributed Computing and Cryptography

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