SWAT 2004

Scientific program

Thursday 8 - Saturday 10 July

Time\Day	Thursday	Friday	Saturday
9.00 - 10.20	Block I opening + 3 talks	Block VI 4 talks	Block XI 4 talks
10.20 - 10.50	Coffee break
10.50 - 11.50	Block II Charles E. Leiserson	Block VII Gerth Stølting Brodal	Block XII 3 talks
11.50 - 12.30	Block III 2 talks	Block VIII 2 talks	Block XIII 2 talks
12.30 - 14.00	Lunch break
14.00 - 15.00	Block IV 3 talks	Block IX 3 talks	Block XIV 3 talks
15.00 - 15.30	Coffee break
15.30 - 16.50	Block V 4 talks	Block X 4 talks	Block XV 3 talks + closing

Detailed program

If known, the speakers are indicated in boldface.

Thursday, block I

Chair: Jyrki Katajainen

Getting the Best Response for Your Erg
Kirk Pruhs, Patchrawat Uthaisombut, and Gerhard Woeginger

Auctions with Budget Constraints
Nir Andelman and Yishay Mansour

Tight Approximability Results for Test Set Problems in Bioinformatics
Piotr Berman, Bhaskar DasGupta, and Ming-Yang Kao

Thursday, block II

Chair: Torben Hagerup

Design and Analysis of Dynamic Multithreaded Algorithms
Charles E. Leiserson

Thursday, block III

Chair: Lene Monrad Favrholdt

Robust Subgraphs for Trees and Paths
Refael Hassin and Danny Segev

Collective Tree Spanners of Graphs
Feodor F. Dragan, Chenyu Yan, and Irina Lomonosov

Thursday, block IV

Chair: Kim Skak Larsen

Optimally Competitive List Batching
Wolfgang W. Bein, Leah Epstein, Lawrence L. Larmore, and John Noga

The Relative Worst Order Ratio Applied to Seat Reservation
Joan Boyar and Paul Medvedev

Online Maintenance of k-Medians and k-Covers on a Line
Rudolf Fleischer, Mordecai J. Golin, and Zhang Yan

Thursday, block V

Chair: Amos Fiat

Matching Polyhedral Terrains Using Overlays of Envelopes
Vladlen Koltun and Carola Wenk

Independent Set of Intersection Graphs of Convex Objects in 2D
Pankaj K. Agarwal and Nabil H. Mustafa (to be presented by Lars Arge)

Maximizing the Area of Overlap of Two Unions of Disks under Rigid Motion
Mark de Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René van Oostrum, and Remco C. Veltkamp

Construction of the Nearest Neighbor Embracing Graph of a Point Set
M.Y. Chan, Danny Chen, Francis Y.L. Chin, and Cao An Wang

Friday, block VI

Chair: Camil Demetrescu

Connectivity of Graphs Under Edge Flips
Norbert Zeh

Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity
Miroslav Chlebík and Janka Chlebíková

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension
Michel Habib, Fabien de Montgolfier, and Christophe Paul

Railway Delay Management: Exploring Its Algorithmic Complexity
Michael Gatto, Björn Glaus, Riko Jacob, Leon Peeters, and Peter Widmayer

Friday, block VII

Chair: Anna Pagh

Cache-Oblivious Algorithms and Data Structures
Gerth Stølting Brodal

Friday, block VIII

Chair: Marina Papatriantafilou

Layered Heaps
Amr Elmasry

Melding Priority Queues
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, and Uri Zwick

Friday, block IX

Chair: Gudmund Skovbjerg Frandsen

An Algorithm for Cyclic Edge Connectivity of Cubic Graphs
Zdenek Dvorák, Jan Kára, Daniel Král', and Ondrej Pangrác

Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices
Anders Dessmark, Andrzej Lingas, and Eva-Marta Lundell

New Algorithms for Enumerating All Maximal Cliques
Kazuhisa Makino and Takeaki Uno

Friday, block X

Chair: Leah Epstein

The Multi-Multiway Cut Problem
Adi Avidor and Michael Langberg

The Bottleneck Problem with Minimum Quantity Commitments
Andrew Lim and Zhou Xu

All-Norm Approximation for Scheduling on Identical Machines
Yossi Azar and Shai Taub

Approximation Algorithms for the General Max-Min Resource Sharing Problem: Faster and Simpler
Klaus Jansen

Saturday, block XI

Chair: Rolf Niedermeier

Approximation Schemes for the Crane Scheduling Problem
Andrew Lim, Brian Rodrigues, and Zhou Xu

Improved Approximation Algorithms for the Single-Sink Buy-At-Bulk Network Design Problems
Raja Jothi and Balaji Raghavachari

A (2 - c log N/N)-Approximation Algorithm for the Stable Marriage Problem
Kazuo Iwama, Shuichi Miyazaki, and Kazuya Okamoto

Maximizing the Number of Packed Rectangles
Klaus Jansen and Guochuan Zhang

Saturday, block XII

Chair: Gerth Stølting Brodal

Two Space Saving Tricks for Linear Time LCP Array Computation
Giovanni Manzini

Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles
Mikkel Thorup

Faster Deterministic Gossiping in Directed Ad-Hoc Radio Networks
Leszek Gasieniec, Tomasz Radzik, and Qin Xin

Saturday, block XIII

Chair: Joan Boyar

Online Scheduling of Splittable Tasks in Peer-To-Peer Networks
Leah Epstein and Rob van Stee

The Optimal Online Algorithms for Minimizing Maximum Lateness
Patchrawat Uthaisombut

Saturday, block XIV

Chair: Bengt J. Nilsson

Power Assignment in Radio Networks with Two Power Levels
Paz Carmi and Matthew J. Katz

Pointed Binary Encompassing Trees
Michael Hoffmann, Bettina Speckmann, and Csaba D. Tóth

On Geometric Structure of Global Roundings for Graphs and Range Spaces
Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama

Saturday, block XV

Chair: Torben Hagerup

External Connected Components
Jop F. Sibeyn

Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths
Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh

Simplified External Memory Algorithms for Planar DAGs
Lars Arge and Laura Toma