Algorithms and Computation : 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings

Invited Talks.- Stable Matching Problems.- Delaunay Meshing of Surfaces.- Best Paper 2006.- Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction.- Best Student Paper 2006.- Branching and Treewidth Based Exact Algorithms.- Session 1A: Algorithms and Data Structures.- Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees.- Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules.- Flexible Word Design and Graph Labeling.- Session 1B: Online Algorithms.- Frequency Allocation Problems for Linear Cellular Networks.- Finite-State Online Algorithms and Their Automated Competitive Analysis.- Offline Sorting Buffers on Line.- Session 2A: Approximation Algorithms.- Approximating Tree Edit Distance Through String Edit Distance.- A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees.- Improved Approximation for Single-Sink Buy-at-Bulk.- Approximability of Partitioning Graphs with Supply and Demand.- Session 2B: Graphs.- Convex Grid Drawings of Plane Graphs with Rectangular Contours.- Algorithms on Graphs with Small Dominating Targets.- Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems.- On Estimating Path Aggregates over Streaming Graphs.- Session 3A: Computational Geometry.- Diamond Triangulations Contain Spanners of Bounded Degree.- Optimal Construction of the City Voronoi Diagram.- Relations Between Two Common Types of Rectangular Tilings.- Quality Tetrahedral Mesh Generation for Macromolecules.- On Approximating the TSP with Intersecting Neighborhoods.- Session 3B: Computational Complexity.- Negation-Limited Complexity of Parity and Inverters.- The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem.- Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete.- Parameterized Problems on Coincidence Graphs.- On 2-Query Codeword Testing with Near-Perfect Completeness.- Session 4A: Algorithms and Data Structures.- Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance.- Efficient Algorithms for the Optimal-Ratio Region Detection Problems in Discrete Geometry with Applications.- On Locating Disjoint Segments with Maximum Sum of Densities.- Two-Tier Relaxed Heaps.- Session 4B: Games and Networks.- The Interval Liar Game.- How Much Independent Should Individual Contacts Be to Form a Small–World?.- Faster Centralized Communication in Radio Networks.- On the Runtime and Robustness of Randomized Broadcasting.- Session 5A: Combinatorial Optimization and Computational Biology.- Local Search in Evolutionary Algorithms: The Impact of the Local Search Frequency.- Non-cooperative Facility Location and Covering Games.- Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees.- Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications.- Algorithms for Computing Variants of the Longest Common Subsequence Problem.- Session 5B: Graphs.- Constructing Labeling Schemes Through Universal Matrices.- Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions.- Analyzing Disturbed Diffusion on Networks.- Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs.- On Isomorphism and Canonization of Tournaments and Hypertournaments.- Session 6A: Algorithms and Data Structures.- Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem.- Deterministic Random Walks on the Two-Dimensional Grid.- Improving Time and Space Complexity for Compressed Pattern Matching.- Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems.- Session 6B: Graphs.- A Simple Message Passing Algorithm for Graph Partitioning Problems.- Minimal Interval Completion Through Graph Exploration.- Balanced Cut Approximation in Random Geometric Graphs.- Improved Algorithms for the Minmax-Regret 1-Center Problem.- Session 7A: Approximation Algorithms.- On Approximating the Maximum Simple Sharing Problem.- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures.- Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems.- Session 7B: Graphs.- Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii.- Efficient Prüfer-Like Coding and Counting Labelled Hypertrees.- Intuitive Algorithms and t-Vertex Cover.- Session 8A: Combinatorial Optimization and Quantum Computing.- Politician’s Firefighting.- Runtime Analysis of a Simple Ant Colony Optimization Algorithm.- Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems.- Resources Required for Preparing Graph States.- Session 8B: Online Algorithms.- Online Multi-path Routing in a Maze.- On the On-Line k-Truck Problem with Benefit Maximization.- Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels.- Online Packet Admission and Oblivious Routing in Sensor Networks.- Session 9A: Computational Geometry.- Field Splitting Problems in Intensity-Modulated Radiation Therapy.- Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy.- A New Approximation Algorithm for Multidimensional Rectangle Tiling.- Tessellation of Quadratic Elements.- Session 9B: Distributed Computing and Cryptography.- Effective Elections for Anonymous Mobile Agents.- Gathering Asynchronous Oblivious Mobile Robots in a Ring.- Provably Secure Steganography and the Complexity of Sampling.