Algorithms and Data Structures: 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 – August 1, 2003. Proceedings

Gilles Brassard, Anne Broadbent, Alain Tapp (auth.), Frank Dehne, Jörg-Rüdiger Sack, Michiel Smid (eds.)3540405453, 9783540405450

This book constitutes the refereed proceedings of the 8th International Workshop on Algorithms and Data Structures, WADS 2003, held in Ottawa, Ontario, Canada, in July/August 2003.

The 40 revised full papers presented together with 4 invited papers were carefully reviewed and selected from 126 submissions. A broad variety of current aspects in algorithmics and data structures is addressed.

---

Table of contents :
Front Matter….Pages –
Multi-party Pseudo-Telepathy….Pages 1-11
Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips….Pages 12-24
Shape Segmentation and Matching with Flow Discretization….Pages 25-36
Phylogenetic Reconstruction from Gene-Rearrangement Data with Unequal Gene Content….Pages 37-46
Toward Optimal Motif Enumeration….Pages 47-58
Common-Deadline Lazy Bureaucrat Scheduling Problems….Pages 59-66
Bandwidth-Constrained Allocation in Grid Computing….Pages 67-78
Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection….Pages 79-90
Fast Algorithms for a Class of Temporal Range Queries….Pages 91-102
Distribution-Sensitive Binomial Queues….Pages 103-113
Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees….Pages 114-126
Extremal Configurations and Levels in Pseudoline Arrangements….Pages 127-139
Fast Relative Approximation of Potential Fields….Pages 140-149
The One-Round Voronoi Game Replayed….Pages 150-161
Integrated Prefetching and Caching with Read and Write Requests….Pages 162-173
Online Seat Reservations via Offline Seating Arrangements….Pages 174-185
Routing and Call Control Algorithms for Ring Networks….Pages 186-197
Algorithms and Models for Railway Optimization….Pages 198-206
Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles….Pages 207-218
Multi-way Space Partitioning Trees….Pages 219-230
Cropping-Resilient Segmented Multiple Watermarking….Pages 231-242
On Simultaneous Planar Graph Embeddings….Pages 243-255
Smoothed Analysis….Pages 256-270
Approximation Algorithm for Hotlink Assignments in Web Directories….Pages 271-280
Drawing Graphs with Large Vertices and Thick Edges….Pages 281-293
Semi-matchings for Bipartite Graphs and Load Balancing….Pages 294-306
The Traveling Salesman Problem for Cubic Graphs….Pages 307-318
Sorting Circular Permutations by Reversal….Pages 319-328
An Improved Bound on Boolean Matrix Multiplication for Highly Clustered Data….Pages 329-339
Dynamic Text and Static Pattern Matching….Pages 340-352
Real Two Dimensional Scaled Matching….Pages 353-364
Proximity Structures for Geometric Graphs….Pages 365-376
The Zigzag Path of a Pseudo-Triangulation….Pages 377-388
Alternating Paths along Orthogonal Segments….Pages 389-400
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem….Pages 401-411
Chips on Wafers….Pages 412-423
A Model for Analyzing Black-Box Optimization….Pages 424-438
On the Hausdorff Voronoi Diagram of Point Clusters in the Plane….Pages 439-450
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries….Pages 451-461
Significant-Presence Range Queries in Categorical Data….Pages 462-473
Either/Or: Using Vertex Cover Structure in Designing FPT -Algorithms — the Case of k – Internal Spanning Tree ….Pages 474-483
Parameterized Complexity of Directed Feedback Set Problems in Tournaments….Pages 484-492
Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs….Pages 493-504
New Directions and New Challenges in Algorithm Design and Complexity, Parameterized….Pages 505-519
Back Matter….Pages –