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

by Dehne, Frank; Sack, Jorg-Rudiger; Smid, Michiel

• ISBN13: 9783540405450
• ISBN10: 3540405453
• Format: Paperback
• Copyright: 2003-08-01
• Publisher: Springer Verlag

Summary

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

Multi-party Pseudo-Telepathy	1	(11)
Gilles Brassard
Anne Broadbent
Alain Tapp
Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips	12	(13)
Oswin Aichholzer
Franz Aurenhammer
Hannes Krasser
Shape Segmentation and Matching with Flow Discretization	25	(12)
Tamal K. Dey
Joachim Giesen
Samrat Goswami
Phylogenetic Reconstruction from Gene-Rearrangement Data with Unequal Gene Content	37	(10)
Jijun Tang
Bernard M.E. Moret
Toward Optimal Motif Enumeration	47	(12)
Patricia A. Evans
Andrew D. Smith
Common-Deadline Lazy Bureaucrat Scheduling Problems	59	(8)
Behdad Esfahbod
Mohammad Ghodsi
Ali Sharifi
Bandwidth-Constrained Allocation in Grid Computing	67	(12)
Anshul Kothari
Subhash Suri
Yunhong Zhou
Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection	79	(12)
Sudipta Sengupta
Fast Algorithms for a Class of Temporal Range Queries	91	(12)
Qingmin Shi
Joseph JaJa
Distribution-Sensitive Binomial Queues	103	(11)
Amr Elmasry
Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees	114	(13)
Gianni Franceschini
Roberto Grossi
Extremal Configurations and Levels in Pseudoline Arrangements	127	(13)
Micha Sharir
Shakhar Smorodinsky
Fast Relative Approximation of Potential Fields	140	(10)
Martin Ziegler
The One-Round Voronoi Game Replayed	150	(12)
Sandor P. Fekete
Henk Meijer
Integrated Prefetching and Caching with Read and Write Requests	162	(12)
Susanne Albers
Markus Buttner
Online Seat Reservations via Offline Seating Arrangements	174	(12)
Jens S. Frederiksen
Kim S. Larsen
Routing and Call Control Algorithms for Ring Networks	186	(12)
R. Sai Anand
Thomas Erlebach
Algorithms and Models for Railway Optimization	198	(9)
Dorothea Wagner
Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles	207	(12)
Matthias Muller-Hannemann
Sven Peyer
Multi-way Space Partitioning Trees	219	(12)
Christian A. Duncan
Cropping-Resilient Segmented Multiple Watermarking	231	(12)
Keith Frikken
Mikhail Atallah
On Simultaneous Planar Graph Embeddings	243	(13)
P. Brass, E. Cenek
Christian A. Duncan
A. Efrat
C. Erten
D. Ismailescu
S.G. Kobourov
A. Lubiw
J.S.B. Mitchell
Smoothed Analysis (Motivation and Discrete Models)	256	(15)
Daniel A. Spielman
Shang-Hua Teng
Approximation Algorithm for Hotlink Assignments in Web Directories	271	(10)
Rachel Matichin
David Peleg
Drawing Graphs with Large Vertices and Thick Edges	281	(13)
Gill Barequet
Michael T. Goodrich
Chris Riley
Semi-matchings for Bipartite Graphs and Load Balancing	294	(13)
Nicholas J.A. Harvey
Richard E. Ladner
Laszlo Lovasz
Tami Tamir
The Traveling Salesman Problem for Cubic Graphs	307	(12)
David Eppstein
Sorting Circular Permutations by Reversal	319	(10)
Andrew Solomon
Paul Sutcliffe
Raymond Lister
An Improved Bound on Boolean Matrix Multiplication for Highly Clustered Data	329	(11)
Leszek Gosieniec
Andrzej Lingas
Dynamic Text and Static Pattern Matching	340	(13)
Amihood Amir
Gad M. Landau
Moshe Lewenstein
Dina Sokol
Real Two Dimensional Scaled Matching	353	(12)
Amihood Amir
Ayelet Butman
Moshe Lewenstein
Ely Porat
Proximity Structures for Geometric Graphs	365	(12)
Sanjiv Kapoor
Xiang-Yang Li
The Zigzag Path of a Pseudo-Triangulation	377	(12)
Oswin Aichholzer
Gunter Rote
Bettina Speckmann
Ileana Streinu
Alternating Paths along Orthogonal Segments	389	(12)
Csaba D. Toth
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem	401	(11)
Marek Karpinski
Ion I. Mandoiu
Alexander Olshevsky
Alexander Zelikovsky
Chips on Wafers	412	(12)
Mattias Andersson
Joachim Gudmundsson
Christos Levcopoulos
A Model for Analyzing Black-Box Optimization	424	(15)
Vinhthuy Phan
Steven Skiena
Pavel Sumazin
On the Hausdorff Voronoi Diagram of Point Clusters in the Plane	439	(12)
Evanthia Papadopoulou
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries	451	(11)
David Bremner
Erik Demaine
Jeff Erickson
John Iacono
Stefan Langerman
Pat Morin
Godfried Toussaint
Significant-Presence Range Queries in Categorical Data	462	(12)
Mark de Berg
Herman J. Haverkort
Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms - The Case of k-Internal Spanning Tree	474	(10)
Elena Prieto
Christian Sloper
Parameterized Complexity of Directed Feedback Set Problems in Tournaments	484	(9)
Venkatesh Raman
Saket Saurabh
Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs	493	(12)
Huaming Zhang
Xin He
New Directions and New Challenges in Algorithm Design and Complexity, Parameterized	505	(16)
Michael R. Fellows
Author Index	521