Algorithm Theory - SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings

Front Matter....Pages -
Design and Analysis of Dynamic Multithreaded Algorithms....Pages 1-2
Cache-Oblivious Algorithms and Data Structures....Pages 3-13
Getting the Best Response for Your Erg....Pages 14-25
Auctions with Budget Constraints....Pages 26-38
Tight Approximability Results for Test Set Problems in Bioinformatics....Pages 39-50
Robust Subgraphs for Trees and Paths....Pages 51-63
Collective Tree Spanners of Graphs....Pages 64-76
Optimally Competitive List Batching....Pages 77-89
The Relative Worst Order Ratio Applied to Seat Reservation....Pages 90-101
Online Maintenance of k -Medians and k -Covers on a Line....Pages 102-113
Matching Polyhedral Terrains Using Overlays of Envelopes....Pages 114-126
Independent Set of Intersection Graphs of Convex Objects in 2D....Pages 127-137
Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion....Pages 138-149
Construction of the Nearest Neighbor Embracing Graph of a Point Set....Pages 150-160
Connectivity of Graphs Under Edge Flips....Pages 161-173
Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity....Pages 174-186
A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension....Pages 187-198
Railway Delay Management: Exploring Its Algorithmic Complexity....Pages 199-211
Layered Heaps....Pages 212-222
Melding Priority Queues....Pages 223-235
An Algorithm for Cyclic Edge Connectivity of Cubic Graphs....Pages 236-247
Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices....Pages 248-259
New Algorithms for Enumerating All Maximal Cliques....Pages 260-272
The Multi-multiway Cut Problem....Pages 273-284
The Bottleneck Problem with Minimum Quantity Commitments....Pages 285-297
All-Norm Approximation for Scheduling on Identical Machines....Pages 298-310
Approximation Algorithms for the General Max-min Resource Sharing Problem: Faster and Simpler....Pages 311-322
Approximation Schemes for the Crane Scheduling Problem....Pages 323-335
Improved Approximation Algorithms for the Single-Sink Buy-at-Bulk Network Design Problems....Pages 336-348
A ( $2 - c\\frac{{\\rm log} N}{N}$ )–Approximation Algorithm for the Stable Marriage Problem....Pages 349-361
Maximizing the Number of Packed Rectangles....Pages 362-371
Two Space Saving Tricks for Linear Time LCP Array Computation....Pages 372-383
Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles....Pages 384-396
Faster Deterministic Gossiping in Directed Ad Hoc Radio Networks....Pages 397-407
Online Scheduling of Splittable Tasks in Peer-to-Peer Networks....Pages 408-419
The Optimal Online Algorithms for Minimizing Maximum Lateness....Pages 420-430
Power Assignment in Radio Networks with Two Power Levels....Pages 431-441
Pointed Binary Encompassing Trees....Pages 442-454
On Geometric Structure of Global Roundings for Graphs and Range Spaces....Pages 455-467
External Connected Components....Pages 468-479
Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths....Pages 480-492
Simplified External Memory Algorithms for Planar DAGs....Pages 493-503
Back Matter....Pages -