Publisher Description

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.

Notes

Also available online

Table of Contents

Multi-party Pseudo-Telepathy.- Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips.- Shape Segmentation and Matching with Flow Discretization.- Phylogenetic Reconstruction from Gene-Rearrangement Data with Unequal Gene Content.- Toward Optimal Motif Enumeration.- Common-Deadline Lazy Bureaucrat Scheduling Problems.- Bandwidth-Constrained Allocation in Grid Computing.- Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection.- Fast Algorithms for a Class of Temporal Range Queries.- Distribution-Sensitive Binomial Queues.- Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees.- Extremal Configurations and Levels in Pseudoline Arrangements.- Fast Relative Approximation of Potential Fields.- The One-Round Voronoi Game Replayed.- Integrated Prefetching and Caching with Read and Write Requests.- Online Seat Reservations via Offline Seating Arrangements.- Routing and Call Control Algorithms for Ring Networks.- Algorithms and Models for Railway Optimization.- Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles.- Multi-way Space Partitioning Trees.- Cropping-Resilient Segmented Multiple Watermarking.- On Simultaneous Planar Graph Embeddings.- Smoothed Analysis.- Approximation Algorithm for Hotlink Assignments in Web Directories.- Drawing Graphs with Large Vertices and Thick Edges.- Semi-matchings for Bipartite Graphs and Load Balancing.- The Traveling Salesman Problem for Cubic Graphs.- Sorting Circular Permutations by Reversal.- An Improved Bound on Boolean Matrix Multiplication for Highly Clustered Data.- Dynamic Text and Static Pattern Matching.- Real Two Dimensional Scaled Matching.- Proximity Structures for Geometric Graphs.- The Zigzag Path of a Pseudo-Triangulation.- Alternating Paths along Orthogonal Segments.- Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem.- Chips on Wafers.- A Model for Analyzing Black-Box Optimization.- On the Hausdorff Voronoi Diagram of Point Clusters in the Plane.- Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.- Significant-Presence Range Queries in Categorical Data.- Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms — the Case of k-Internal Spanning Tree.- Parameterized Complexity of Directed Feedback Set Problems in Tournaments.- Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs.- New Directions and New Challenges in Algorithm Design and Complexity, Parameterized.

Promotional

Also available online

Long Description

The papers in this volume were presented at the 8th Workshop on Algorithms and Data Structures (WADS 2003). The workshop took place July 30-August 1, 2003, at Carleton University in Ottawa, Canada. The workshop alternates with the Scandinavian Workshop on Algorithm Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the call for papers, 126 papers were submitted. From these submissions, the program committee selected 40 papers for presentation at the workshop. In addition, invited lectures were given by the following distinguished researchers: Gilles Brassard, Dorothea Wagner, Daniel Spielman, and Michael Fellows. Atthisyear'sworkshop,(NelliganO'BrienPayneLLP,Ottawa) gave a special presentation on "Protecting Your Intellectual Property." On July 29, Hans-Georg Zimmermann (Siemens AG, Munc

Details