Algorithms and Computation

Zusammenfassung

This book constitutes the refereed proceedings of the 17th International Symposium on Algorithms and Computation, ISAAC 2006, held in Kolkata, India, December 2006. The 73 revised full papers cover algorithms and data structures, online algorithms, approximation algorithm, computational geometry, computational complexity, optimization and biology, combinatorial optimization and quantum computing, as well as distributed computing and cryptography.

Inhalt
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 MinimumGenerating 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 SmallWorld?.- 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.- Session9B: 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.