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

Front Matter....Pages -
Stable Matching Problems....Pages 1-1
Delaunay Meshing of Surfaces....Pages 2-2
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction....Pages 3-15
Branching and Treewidth Based Exact Algorithms....Pages 16-25
Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees....Pages 26-35
Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules....Pages 36-47
Flexible Word Design and Graph Labeling....Pages 48-60
Frequency Allocation Problems for Linear Cellular Networks....Pages 61-70
Finite-State Online Algorithms and Their Automated Competitive Analysis....Pages 71-80
Offline Sorting Buffers on Line....Pages 81-89
Approximating Tree Edit Distance Through String Edit Distance....Pages 90-99
A 6-Approximation Algorithm for Computing Smallest Common AoN-Supertree with Application to the Reconstruction of Glycan Trees....Pages 100-110
Improved Approximation for Single-Sink Buy-at-Bulk....Pages 111-120
Approximability of Partitioning Graphs with Supply and Demand....Pages 121-130
Convex Grid Drawings of Plane Graphs with Rectangular Contours....Pages 131-140
Algorithms on Graphs with Small Dominating Targets....Pages 141-152
Efficient Algorithms for Weighted Rank-Maximal Matchings and Related Problems....Pages 153-162
On Estimating Path Aggregates over Streaming Graphs....Pages 163-172
Diamond Triangulations Contain Spanners of Bounded Degree....Pages 173-182
Optimal Construction of the City Voronoi Diagram....Pages 183-192
Relations Between Two Common Types of Rectangular Tilings....Pages 193-202
Quality Tetrahedral Mesh Generation for Macromolecules....Pages 203-212
On Approximating the TSP with Intersecting Neighborhoods....Pages 213-222
Negation-Limited Complexity of Parity and Inverters....Pages 223-232
The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem....Pages 233-242
Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete....Pages 243-252
Parameterized Problems on Coincidence Graphs....Pages 253-266
On 2-Query Codeword Testing with Near-Perfect Completeness....Pages 267-276
Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance....Pages 277-288
Efficient Algorithms for the Optimal-Ratio Region Detection Problems in Discrete Geometry with Applications....Pages 289-299
On Locating Disjoint Segments with Maximum Sum of Densities....Pages 300-307
Two-Tier Relaxed Heaps....Pages 308-317
The Interval Liar Game....Pages 318-327
How Much Independent Should Individual Contacts Be to Form a Small–World?....Pages 328-338
Faster Centralized Communication in Radio Networks....Pages 339-348
On the Runtime and Robustness of Randomized Broadcasting....Pages 349-358
Local Search in Evolutionary Algorithms: The Impact of the Local Search Frequency....Pages 359-368
Non-cooperative Facility Location and Covering Games....Pages 369-378
Optimal Algorithms for the Path/Tree-Shaped Facility Location Problems in Trees....Pages 379-388
Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications....Pages 389-398
Algorithms for Computing Variants of the Longest Common Subsequence Problem....Pages 399-408
Constructing Labeling Schemes Through Universal Matrices....Pages 409-418
Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions....Pages 419-428
Analyzing Disturbed Diffusion on Networks....Pages 429-438
Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs....Pages 439-448
On Isomorphism and Canonization of Tournaments and Hypertournaments....Pages 449-459
Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem....Pages 460-473
Deterministic Random Walks on the Two-Dimensional Grid....Pages 474-483
Improving Time and Space Complexity for Compressed Pattern Matching....Pages 484-493
Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems....Pages 494-506
A Simple Message Passing Algorithm for Graph Partitioning Problems....Pages 507-516
Minimal Interval Completion Through Graph Exploration....Pages 517-526
Balanced Cut Approximation in Random Geometric Graphs....Pages 527-536
Improved Algorithms for the Minmax-Regret 1-Center Problem....Pages 537-546
On Approximating the Maximum Simple Sharing Problem....Pages 547-556
Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures....Pages 557-566
Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems....Pages 567-577
Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii....Pages 578-587
Efficient Prüfer-Like Coding and Counting Labelled Hypertrees....Pages 588-597
Intuitive Algorithms and t -Vertex Cover....Pages 598-607
Politician’s Firefighting....Pages 608-617
Runtime Analysis of a Simple Ant Colony Optimization Algorithm....Pages 618-627
Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems....Pages 628-637
Resources Required for Preparing Graph States....Pages 638-649
Online Multi-path Routing in a Maze....Pages 650-659
On the On-Line k -Truck Problem with Benefit Maximization....Pages 660-669
Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels....Pages 670-679
Online Packet Admission and Oblivious Routing in Sensor Networks....Pages 680-689
Field Splitting Problems in Intensity-Modulated Radiation Therapy....Pages 690-700
Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy....Pages 701-711
A New Approximation Algorithm for Multidimensional Rectangle Tiling....Pages 712-721
Tessellation of Quadratic Elements....Pages 722-731
Effective Elections for Anonymous Mobile Agents....Pages 732-743
Gathering Asynchronous Oblivious Mobile Robots in a Ring....Pages 744-753
Provably Secure Steganography and the Complexity of Sampling....Pages 754-763
Back Matter....Pages -