Algorithms and Data Structures: 7th International Workshop, WADS 2001 Providence, RI, USA, August 8–10, 2001 Proceedings

Approximation of Multiobjective Optimization Problems....Pages 1-1
Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs....Pages 2-13
Optimal Möbius Transformations for Information Visualization and Meshing....Pages 14-25
Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming....Pages 26-37
On the Complexity of Scheduling Conditional Real-Time Code....Pages 38-49
Time Responsive External Data Structures for Moving Points....Pages 50-61
Voronoi Diagrams for Moving Disks and Applications....Pages 62-74
Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover....Pages 75-86
Deciding Clique-Width for Graphs of Bounded Tree-Width....Pages 87-98
Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions....Pages 99-110
Optimization over Zonotopes and Training Support Vector Machines....Pages 111-121
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions....Pages 122-134
Seller-Focused Algorithms for Online Auctioning....Pages 135-147
Competitive Analysis of the LRFU Paging Algorithm....Pages 148-154
Admission Control to Minimize Rejections....Pages 155-164
Secure Multi-party Computational Geometry....Pages 165-179
The Grid Placement Problem....Pages 180-191
On the Reflexivity of Point Sets....Pages 192-204
A 7/8-Approximation Algorithm for Metric Max TSP....Pages 205-209
Approximating Multi-objective Knapsack Problems....Pages 210-221
Visual Ranking of Link Structures....Pages 222-233
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs....Pages 234-245
Short and Simple Labels for Small Distances and Other Functions....Pages 246-257
Fast Boolean Matrix Multiplication for Highly Clustered Data....Pages 258-263
Partitioning Colored Point Sets into Monochromatic Parts....Pages 264-275
The Analysis of a Probabilistic Approach to Nearest Neighbor Searching....Pages 276-286
I/O-Efficient Shortest Path Queries in Geometric Spanners....Pages 287-299
Higher-Dimensional Packing with Order Constraints....Pages 300-312
Bin Packing with Item Fragmentation....Pages 313-324
Practical Approximation Algorithms for Separable Packing Linear Programs....Pages 325-337
The Challenges of Delivering Content on the Internet....Pages 338-338
Upward Embeddings and Orientations of Undirected Planar Graphs....Pages 339-351
An Approach for Mixed Upward Planarization....Pages 352-364
A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study....Pages 365-376
Computing Phylogenetic Roots with Bounded Degrees and Errors....Pages 377-388
A Decomposition-Based Approach to Layered Manufacturing....Pages 389-400
When Can You Fold a Map?....Pages 401-413
Search Trees with Relaxed Balance and Near-Optimal Height....Pages 414-425
Succinct Dynamic Data Structures....Pages 426-437
Optimal Algorithms for Two-Guard Walkability of Simple Polygons....Pages 438-449
Movement Planning in the Presence of Flows....Pages 450-461
Small Maximal Independent Sets and Faster Exact Graph Coloring....Pages 462-470
On External-Memory Planar Depth First Search....Pages 471-482