Algorithms and Data Structures: 6th International Workshop, Wads'99, Vancouver, Canada, August 11-14, 1999 : Proceedings

by Dehne, Frank; Dehne, Frank; Sack, Jorg-Rudiger; Tamassia, Roberto

• ISBN13: 9783540662792
• ISBN10: 3540662790
• Format: Paperback
• Copyright: 1999-08-01
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the 6th International Workshop on Algorithms and Data Structures, WADS'99, held in Vancouver, Canada, in August 1999.The 32 revised papers presented were carefully reviewed and selected from a total of 71 submissions. Among the topics covered are data structures and algorithmic aspects in a variety of areas such as graph theory, networking, load balancing, optimization, approximation, sorting and searching, pattern matching, information retrieval, computational mathematics, etc.

Table of Contents

Optimization over k-set Polytopes and Efficient k-set Enumeration	p. 1
Line Simplification with Restricted Orientations	p. 13
The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout	p. 25
Resizable Arrays in Optimal Time and Space	p. 37
Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions	p. 49
Design and Analysis of Algorithms for Shared-Memory Multiprocessors	p. 55
On the Complexity of Orthogonal Compaction	p. 56
Optimizing Constrained Offset and Scaled Polygonal Annuli	p. 62
The Accommodating Function - A Generalization of the Competitive Ratio	p. 74
Performance Guarantees for the TSP with a Parameterized Triangle Inequality	p. 80
Robot Map Verification of a Graph World	p. 86
Searching Rectilinear Streets Completely	p. 98
General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time	p. 110
The Lazy Bureaucrat Scheduling Problem	p. 122
Generating 3D Virtual Populations from Pictures of a Few Individuals	p. 134
Testing the Quality of Manufactured Balls	p. 145
On an Optimal Split Tree Problems	p. 157
Representing Trees of Higher Degree	p. 169
Indexing and Dictionary Matching with One Error	p. 181
New Results on Fault Tolerant Geometric Spanners	p. 193
Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences	p. 205
Go-with-the-Winner Heuristic	p. 217
2-Point Site Voronoi Diagrams	p. 219
A Parallel Algorithm for Finding the Constrained Voronoi Diagram of Line Segments in the Plane	p. 231
Position-Independent Street Searching	p. 241
Approximation Algorithms for 3-D Common Substructure Identification in Drug and Protein Molecules	p. 253
A Tight Bound for Beta-Skeleton of Minimum Weight Triangulations	p. 265
Rectilinear Static and Dynamic Discrete 2-Center Problems	p. 276
Gene Trees and Species Trees: The Gene-Duplication Problem is Fixed-Parameter Tractable	p. 288
Efficient Web Searching Using Temporal Factors	p. 294
Elastic Labels Around The Perimeter of a Map	p. 306
Optimal Facility Location under Various Distance Functions	p. 318
Thresholds for Sports Elimination Numbers: Algorithms and Complexity	p. 330
Dynamic Representations of Sparse Graphs	p. 342
Online Data Structures in External Memory	p. 352
Author Index	p. 367
Table of Contents provided by Blackwell. All Rights Reserved.