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

Mihalis Yannakakis (auth.), Frank Dehne, Jörg-Rüdiger Sack, Roberto Tamassia (eds.)3540424237, 9783540424239

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms and Data Structures, WADS 2001, held in Providence, RI, USA in August 2001. The 40 revised full papers presented were carefully reviewed and selected from a total of 89 submissions. Among the topics addressed are multiobjective optimization, computational graph theory, approximation, optimization, combinatorics, scheduling, Varanoi diagrams, packings, multi-party computation, polygons, searching, etc.

---

Table of contents :
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