Algorithm Theory - SWAT 2004

Robust Subgraphs for Trees and Paths

Hassin, Refael (et al.)

Pages 51-63

Collective Tree Spanners of Graphs

Dragan, Feodor F. (et al.)

Pages 64-76

Optimally Competitive List Batching

Bein, Wolfgang W. (et al.)

Pages 77-89

The Relative Worst Order Ratio Applied to Seat Reservation

Boyar, Joan (et al.)

Pages 90-101

Online Maintenance of k-Medians and k-Covers on a Line

Fleischer, Rudolf (et al.)

Pages 102-113

Matching Polyhedral Terrains Using Overlays of Envelopes

Koltun, Vladlen (et al.)

Pages 114-126

Independent Set of Intersection Graphs of Convex Objects in 2D

Agarwal, Pankaj K. (et al.)

Pages 127-137

Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion

Berg, Mark (et al.)

Pages 138-149

Construction of the Nearest Neighbor Embracing Graph of a Point Set

Chan, M. Y. (et al.)

Pages 150-160

Connectivity of Graphs Under Edge Flips

Zeh, Norbert

Pages 161-173

Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity

Chlebík, Miroslav (et al.)

Pages 174-186

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

Habib, Michel (et al.)

Pages 187-198

Railway Delay Management: Exploring Its Algorithmic Complexity

Gatto, Michael (et al.)

Pages 199-211

Layered Heaps

Elmasry, Amr

Pages 212-222

Melding Priority Queues

Mendelson, Ran (et al.)

Pages 223-235

An Algorithm for Cyclic Edge Connectivity of Cubic Graphs

Dvořák, Zdeněk (et al.)

Pages 236-247

Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices

Dessmark, Anders (et al.)

Pages 248-259

New Algorithms for Enumerating All Maximal Cliques

Makino, Kazuhisa (et al.)

Pages 260-272

The Multi-multiway Cut Problem

Avidor, Adi (et al.)

Pages 273-284

The Bottleneck Problem with Minimum Quantity Commitments

Lim, Andrew (et al.)

Pages 285-297

All-Norm Approximation for Scheduling on Identical Machines

Azar, Yossi (et al.)

Pages 298-310

Approximation Algorithms for the General Max-min Resource Sharing Problem: Faster and Simpler

Jansen, Klaus

Pages 311-322

Approximation Schemes for the Crane Scheduling Problem

Lim, Andrew (et al.)

Pages 323-335

Improved Approximation Algorithms for the Single-Sink Buy-at-Bulk Network Design Problems

Jothi, Raja (et al.)

Pages 336-348

A ($2 - c\frac{{\rm log} N}{N}$)–Approximation Algorithm for the Stable Marriage Problem

Iwama, Kazuo (et al.)

Pages 349-361

Maximizing the Number of Packed Rectangles

Jansen, Klaus (et al.)

Pages 362-371

Two Space Saving Tricks for Linear Time LCP Array Computation

Manzini, Giovanni

Pages 372-383

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

Thorup, Mikkel

Pages 384-396

Faster Deterministic Gossiping in Directed Ad Hoc Radio Networks

Gąsieniec, Leszek (et al.)

Pages 397-407

Online Scheduling of Splittable Tasks in Peer-to-Peer Networks

Epstein, Leah (et al.)

Pages 408-419

The Optimal Online Algorithms for Minimizing Maximum Lateness

Uthaisombut, Patchrawat

Pages 420-430

Power Assignment in Radio Networks with Two Power Levels

Carmi, Paz (et al.)

Pages 431-441

Pointed Binary Encompassing Trees

Hoffmann, Michael (et al.)

Pages 442-454

On Geometric Structure of Global Roundings for Graphs and Range Spaces

Asano, Tetsuo (et al.)

Pages 455-467

External Connected Components

Sibeyn, Jop F.

Pages 468-479

Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

Brodal, Gerth Stølting (et al.)

Pages 480-492

Simplified External Memory Algorithms for Planar DAGs

Arge, Lars (et al.)

Pages 493-503