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

Charles E. Leiserson (auth.), Torben Hagerup, Jyrki Katajainen (eds.)3540223398, 9783540223399, 9783540278108

This book constitutes the refereed proceedings of the 9th Scandinavian Workshop on Algorithm Theory, SWAT 2004, held in Humlebaek, Denmark in July 2004.

The 40 revised full papers presented together with an invited paper and the abstract of an invited talk were carefully reviewed and selected from 121 submissions. The papers span the entire range of theoretical algorithmics and applications in various fields including graph algorithms, computational geometry, scheduling, approximation algorithms, network algorithms, data storage and manipulation, bioinformatics, combinatorics, sorting, searching, online algorithms, optimization, etc.

---

Table of contents :
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 – cfrac{{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 –