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

This book constitutes the refereed proceedings of the 17th International Symposium on Algorithms and Computation, ISAAC 2006, held in Kolkata, India in December 2006.

The 73 revised full papers presented were carefully reviewed and selected from 255 submissions. The papers are organized in topical sections on algorithms and data structures, online algorithms, approximation algorithm, graphs, computational geometry, computational complexity, network, optimization and biology, combinatorial optimization and quantum computing, as well as distributed computing and cryptography.

---

This book constitutes the refereed proceedings of the 17th International Symposium on Algorithms and Computation, ISAAC 2006, held in Kolkata, India in December 2006.

The 73 revised full papers presented were carefully reviewed and selected from 255 submissions. The papers are organized in topical sections on algorithms and data structures, online algorithms, approximation algorithm, graphs, computational geometry, computational complexity, network, optimization and biology, combinatorial optimization and quantum computing, as well as distributed computing and cryptography.

Content:
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 -

---

This book constitutes the refereed proceedings of the 17th International Symposium on Algorithms and Computation, ISAAC 2006, held in Kolkata, India in December 2006.

The 73 revised full papers presented were carefully reviewed and selected from 255 submissions. The papers are organized in topical sections on algorithms and data structures, online algorithms, approximation algorithm, graphs, computational geometry, computational complexity, network, optimization and biology, combinatorial optimization and quantum computing, as well as distributed computing and cryptography.

Content:
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 -
....