List of accepted papers for SWAT 2004:


Pankaj K. Agarwal Nabil H. Mustafa
Independent Set of Intersection Graphs of Convex Objects in 2D

Nir Andelman Yishay Mansour
Auctions with Budget Constraints

Lars Arge Laura Toma
Simplified External Memory Algorithms for Planar DAGs

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

Adi Avidor Michael Langberg
The Multi-Multiway Cut Problem

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

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

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

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

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

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

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

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

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

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

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

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

Amr Elmasry
Layered Heaps

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

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

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

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

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

Refael Hassin Danny Segev
Robust Subgraphs for Trees and Paths

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

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

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

Klaus Jansen Guochuan Zhang
Maximizing the Number of Packed Rectangles

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

Vladlen Koltun Carola Wenk
Matching Polyhedral Terrains Using Overlays of Envelopes

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

Andrew Lim Zhou Xu
The Bottleneck Problem with Minimum Quantity Commitments

Kazuhisa Makino Takeaki Uno
New Algorithms for Enumerating All Maximal Cliques

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

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

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

Jop F. Sibeyn
External Connected Components

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

Patchrawat Uthaisombut
The Optimal Online Algorithms for Minimizing Maximum Lateness

Norbert Zeh
Connecivity of Graphs Under Edge Flips