9.00-9.20 - SWAT 2008 Opening

9.20-10.20 - Session 1
Session chair: Philippas Tsigas

Simplified Planar Coresets for Data Streams
John Hershberger and Subhash Suri

Uniquely Represented Data Structures for Computational Geometry
Guy E. Blelloch, Daniel Golovin and Virginia Vassilevska

I/O Efficient Dynamic Data Structures for Longest Prefix Queries
Moshe Hershcovitch and Haim Kaplan

10.50-11.50 - Invited talk 1
Session chair: Peter Bro Miltersen

Vijay Vazirani
Title: Nash Bargaining via Flexible Budget Markets
(Program change)

13.20-14.40 - Session 2
Session chair: Antonios Symvonis

Guarding Art Galleries: The Extra Cost for Sculptures is Linear
Louigi Addario-Berry, Omid Amini, Jean-Sebastien Sereni and Stephan Thomasse

Vision-based pursuit-evasion in a grid
Adrian Dumitrescu, Howi Kok, Ichiro Suzuki and Pawel Zylinski

Angle Optimization in Target Tracking
Beat Gfeller, Matus Mihalak, Subhash Suri, Elias Vicari and Peter Widmayer

Improved Bounds for Wireless Localization
Tobias Christ, Michael Hoffmann, Yoshio Okamoto and Takeaki Uno

15.10-16.30 - Session 3
Session chair: Magnus Haldorsson

Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
Yuval Rabani and Gabriel Scalosub

Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint
Hans Bodlaender, Richard Tan, Thomas C. van Dijk and Jan van Leeuwen

The Maximum Energy-Constrained Dynamic Flow Problem
Sandor Fekete, Alex Hall, Ekkehard Koehler and Alexander Kroeller

Bounded Unpopularity Matchings
Chien-Chung Huang, Telikepalli Kavitha, Dimitrios Michail and Meghana Nasre

16.45-17.45 - Business meeting
Session chair: Magnus Haldorsson

Social: City hall reception

9.00-10.20 - Session 4
Session chair: Michael Mitzenmacher

Data Structures with Local Update Operations Yakov Nekrich

On the redundancy of succinct data structures Alexander Golynski, Rajeev Raman and Srinivasa Rao Satti.

Confluently Persistent Tries for Efficient Version Control
Erik D. Demaine, Stefan Langerman and Eric Price.

A Uniform Approach Towards Succinct Representation of Trees
Arash Farzan and Ian Munro

10.50-11.50 - Invited talk 2
Session chair: Rasmus Pagh

Michael Mitzenmacher
Title: A Survey of Results for Deletion Channels and
Related Synchronization Channels
(Program change)

13.20-14.40 - Session 5
Session chair: Subhash Suri

An O(n^{1.75}) Algorithm for L(2,1)-labeling of Trees
Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno

Batch Coloring Flat Graphs and Thin
Magnús M. Halldórsson and Hadas Shachnai

Approximating the Interval Constrained Coloring Problem
Julian Mestre, Ernst Althaus, Stefan Canzar, Andreas Karrenbauer and Khaled Elbassioni

A Path Cover Technique for LCAs in Dags
Miroslaw Kowaluk, Andrzej Lingas and Johannes Nowak

15.10-16.30 - Session 6
Session chair: Prosenjit Bose

Boundary Labeling with Octilinear Leaders
Michael Bekos, Michael Kaufmann, Martin Nöllenburg and Antonios Symvonis

Distributed Disaster Disclosure
Bernard Mans, Stefan Schmid and Roger Wattenhofer

Reoptimization of Steiner Trees
Davide Bilo, Hans-Joachim Böckenhauer, Juraj Hromkovic, Richard Kralovic,
Tobias Mömke, Peter Widmayer and Anna Zych

On the Locality of Extracting a 2-Manifold in R^3 Daniel Dumitriu, Stefan
Funke, Nikola Milosavljevic and Martin Kutz

16.45-17.45 - Session 7
Session chair: Marina Papatriantafilou

On Metric Clustering to Minimize the Sum of Radii
Matt Gibson, Gaurav Kanade, Erik Krohn, Imran Pirwani and Kasturi Varadarajan

On covering problems of Rado
Sergey Bereg, Adrian Dumitrescu and Minghui Jiang

Packing Rectangles into 2 OPT Bins using Rotations
Rolf Harren and Rob van Stee

18.00

Social: Tour and conference dinner

9.00-10.20 - Session 8
Session chair: John Hershberger

[Best paper award!]
A preemptive algorithm for maximizing disjoint paths on trees
Yossi Azar, Uriel Feige and Daniel Glasner

Minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs
Pinar Heggernes, Daniel Meister and Andrzej
Proskurowski

On a special co-cycle basis of graphs
Telikepalli Kavitha

A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
Min Chih Lin, Francisco Soulignac and Jayme L. Szwarcfiter

10.50-11.50 - Session 9
Session chair: Michael Hoffmann

Spanners of Additively Weighted Point Sets
Prosenjit Bose, Paz Carmi and Mathieu Couture

The Kinetic Facility Location Problem
Bastian Degener, Joachim Gehweiler and Christiane Lammersen

Computing the greedy spanner in near-quadratic time
Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari and Michiel Smid

13.20-14.20 - Session 10
Session chair: Thore Husfeldt

Parameterized Computational Complexity of Dodgson and Young Elections
Nadja Betzler, Jiong Guo and Rolf Niedermeier

Online Compression Caching
Mitul Tiwari, Greg Plaxton, Yu Sun and Harrick Vin

On Trade-Offs in External-Memory Diameter-Approximation
Ulrich Meyer

Closing SWAT 2008