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

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 -