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

ISBN-13: 9783540405450 / Angielski / Miękka / 2003 / 522 str.

Frank Dehne; Jrg Rdiger Sack; Michiel Smid

Opis

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.

Spis treści

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.