Science Meets Art

SWAT 2004

9th Scandinavian Workshop on Algorithm Theory

8–10 July, 2004

Louisiana Museum of Modern Art, Humlebæk, Denmark

SWAT vikings
Accepted papers
Best student paper
Call for papers
Conference shop
Invited speakers
Press release
Related events
Scientific program
Social program
Tourist info

Accepted papers (40 of 121 submissions)

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 Last modified: 09.05.2005