Workshop on Algorithms and Data Structures (WADS 2003)

Prof. Frank Dehne ( frank at
Mon May 26 18:45:22 PDT 2003



     Workshop on Algorithms and Data Structures (WADS 2003) 

    July 30 - August 1, 2003, Carleton Univ., Ottawa, Canada 

Conference Registration: (deadline: June 29)
Hotel Registration: (deadline: June 29)

July 29: Tutorial on Neural Networks 
         (speaker: H.-G.Zimmermann, consult ) 

July 30 - August 1: WADS 

August 2: Workshop and Tutorial on Fixed Parameter Tractability 
          (lead by Mike Fellows, consult ) 

                      WADS Program

Tuesday July 29
6:00 pm - 8:00 pm
WADS registration and welcome reception, foyer Tory Building

Wednesday July 30
9:30 - 10:30: 

Session 1: 

invited talk: Quantum Communication Complexity, 
by Gilles Brassard 

10:30 - 11:00: coffee 

11:00 - 12:00: 

Session 2A: 

Adapting (Pseudo)-Triangulations with a Near-Linear 
Number of Edge Flips, Oswin Aichholzer, Franz 
Aurenhammer, Hannes Krasser

Shape Segmentation and Matching with Flow Discretization,
Tamal Dey, Joachim Giesen, Samrat Goswami 

Session 2B: 

Phylogenetic Reconstruction from Gene Rearrangement 
Data with Unequal Gene Content, Jijun Tang, 
Bernard Moret 

Toward Optimal Motif Enumeration, Patricia Evans, 
Andrew Smith 

1:30 - 3:00: 

Session 3A: 

Common-Deadline Lazy Bureaucrat Scheduling Problems, 
Behdad Esfahbo, Mohammad Ghodsi, Ali Sharifi 

Bandwidth-Constrained Allocation in Grid Computing, 
Anshul Kothari, Subhash Suri, Yunhong Zhou

Algorithms and Approximation Schemes for Minimum 
Lateness/Tardiness Scheduling with Rejection, 
Sudipta Sengupta

Session 3B: 

Fast Algorithms for a Class of Temporal Range Queries, 
Qingmin Shi, Joseph JaJa 

Distribution-Sensitive Binomial Queues, Amr Elmasry 

Optimal Worst-Case Operations for Implicit 
Cache-Oblivious Search Trees, Gianni Franceschini, 
Roberto Grossi

3:00 - 3:30: coffee 

3:30 - 5:00: 

Session 4A: 

Extremal Configurations and Levels in Pseudoline Arrangements, 
Micha Sharir, Shakhar Smorodinsky 

Fast Relative Approximation of Potential Fields, 
Martin Ziegler 

The one-round Voronoi game replayed, Sandor Fekete, 
Henk Meijer

Session 4B: 

Integrated Prefetching and Caching with Read and Write 
Requests, Susanne Albers, Markus Buttner

On-Line Seat Reservations via Off-Line Seating 
Arrangements, Jens S. Frederiksen, Kim S. Larsen 

Routing and Call Control Algorithms for Ring Networks, 
R. Sai Anand, Thomas Erlebach

5:15 - 6:00: 

Special Presentation: Protecting your intellectual property,
Wing T. Yan 

Thursday July 31
9:30 - 10:30: 

Session 5: 

invited talk: Algorithms and Models for Railway 
Optimization, by Dorothea Wagner 

10:30 - 11:00: coffee 

11:00 - 12:00: 

Session 6A: 

Approximation of Rectilinear Steiner Trees with Length 
Restrictions on Obstacles, Matthias Muller-Hannemann, 
Sven Peyer

On the Hausdorff Voronoi diagram of point clusters 
in the plane, Evanthia Papadopoulou 

Session 6B:

Cropping-Resilient Segmented Multiple Watermarking, 
Keith Frikken, Mikhail Atallah 

On Simultaneous Planar Graph Embeddings, 
P. Brass, E. Cenek, C. Duncan, A. Efrat,
C. Erten, D. Ismailescu, S. Kobourov,
A. Lubiw, J. Mitchell

1:30 - 2:30: 

Session 7: 

invited talk: Perturbation Models for Smoothed 
Analysis, by Daniel Spielman 

2:30 - 3:00: coffee 

3:00 - 5:00: 

Session 8A: 

Approximation Algorithm for Hotlink Assignments in Web 
Directories, Rachel Matichin, David Peleg 

Drawing Graphs with Large Vertices and Thick Edges, 
Gill Barequet, Michael T. Goodrich, Chris Riley 

Semi-Matchings for Bipartite Graphs and Load Balancing, 
Nicholas Harvey, Richard Ladner, Laszlo Lovasz, Tami 

The Traveling Salesman Problem for Cubic Graphs, 
David Eppstein 

Session 8B: 

Sorting circular permutations by reversal, 
Andrew Solomon, Paul Sutcliffe, Raymond Lister 

An improved bound on Boolean matrix multiplication for 
highly clustered data, Leszek Gasieniec, Andrzej Lingas

Dynamic Text and Static Pattern Matching, 
Amihood Amir, Gad Landau, Moshe Lewenstein, Dina Sokol

Real Two Dimensional Scaled Matching, 
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat 

Conference dinner at the Chateau Laurier, starting at 7pm. 

Friday August 1
9:00 - 10:30: 

Session 9A: 

Proximity Structures for Geometric graphs, 
Sanjiv Kapoor, Xiang-Yang Li 

The Zigzag Path of a Pseudo-Triangulation, 
Oswin Aichholzer, Guenter Rote, Bettina Speckmann, 
Ileana Streinu 

Alternating Paths along Orthogonal Segmenta, Csaba Toth 

Session 9B: 

Improved Approximation Algorithms for the Quality of 
Service Steiner Tree Problem, Marek Karpinski, 
Ion Mandoiu, Alex Olshevsky, Alexander Zelikovsky 

Chips on Wafers, or Packing Rectangles into Grids, 
Mattias Andersson, Joachim Gudmundsson, 
Christos Levcopoulos 

A Model for Analyzing Black-Box Optimization, 
Pavel Sumazin, Vinhthuy Phan, Steve Skiena 

10:30 - 11:00: coffee 

11:00 - 12:30: 

Session 10A: 

Multi-way Space Partitioning Trees, Christian Duncan

Output-Sensitive Algorithms for Computing 
Nearest-Neighbour Decision Boundaries, 
David Bremner, Erik Demaine, Jeff Erickson,
John Iacono, Stefan Langerman, Pat Morin,
Godfried Toussaint

Significant-Presence Range Queries in Categorical Data,
Mark de Berg, Herman J. Haverkort

Session 10B: 

Either/Or: Using Vertex Cover Structure in designing 
FPT-algorithms - the case of k-Internal Spanning Tree,
Elena Prieto, Christian Sloper

Parameterized Complexity of Directed Feedback Set 
Problems in Tournaments, Venkatesh Raman, Saket Saurabh

Compact Visibility Representation and Straight-Line Grid 
Embedding of Plane Graphs, Huaming Zhang, Xin He

2:00 - 3:00: 

Session 11:

invited talk: New Directions and New Challenges 
in Algorithm Design and Complexity, Parameterized, 
by Michael Fellows 

3:00 - 3:30: coffee 


The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list