9783540223399

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.

Design and analysis of dynamic multithreaded algorithms	p. 1
Cache-oblivious algorithms and data structures	p. 3
Getting the best response for your Erg	p. 14
Auctions with budget constraints	p. 26
Tight approximability results for test set problems in bioinformatics	p. 39
Robust subgraphs for trees and paths	p. 51
Collective tree spanners of graphs	p. 64
Optimally competitive list batching	p. 77
The relative worst order ratio applied to seat reservation	p. 90
Online maintenance of k-meridians and k-covers on a line	p. 102
Matching polyhedral terrains using overlays of envelopes	p. 114
Independent set of intersection graphs of convex objects in 2D	p. 127
Maximizing the area of overlap of two unions of disks under rigid motion	p. 138
Construction of the nearest neighbor embracing graph of a point set	p. 150
Connectivity of graphs under edge flips	p. 161
Improvement of Nemhauser-Trotter theorem and its applications in parametrized complexity	p. 174
A simple linear-time modular decomposition algorithm for graphs, using order extension	p. 187
Railway delay management : exploring its algorithmic complexity	p. 199
Layered heaps	p. 212
Melding priority queues	p. 223
An algorithm for cyclic edge connectivity of cubic graphs	p. 236
Subexponential-time framework for optimal embeddings of graphs in integer lattices	p. 248
New algorithms for enumerating all maximal cliques	p. 260
The multi-multiway cut problem	p. 273
The bottleneck problem with minimum quantity commitments	p. 285
All-norm approximation for scheduling on identical machines	p. 298
Approximation algorithms for the general max-min resource sharing problem : faster and simpler	p. 311
Approximation schemes for the crane scheduling problem	p. 323
Improved approximation algorithms for the single-sink buy-at-bulk network design problems	p. 336
A (2 - c[actual symbol not reproducible])-approximation for the stable marriage problem	p. 349
Maximizing the number of packed rectangles	p. 362
Two space saving tricks for linear time LCP array computation	p. 372
Fully-dynamic all-pairs shortest paths : faster and allowing negative cycles	p. 384
Faster deterministic gossiping in directed ad hoc radio networks	p. 397
Online scheduling of splittable tasks in peer-to-peer networks	p. 408
The optimal online algorithms for minimizing maximum lateness	p. 420
Power assignment in radio networks with two power levels	p. 431
Pointed binary encompassing trees	p. 442
On geometric structure of global roundings for graphs and range spaces	p. 455
External connected components	p. 468
Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths	p. 480
Simplified external memory algorithms for planar DAGs	p. 493
Table of Contents provided by Blackwell. All Rights Reserved.

Supplemental Materials

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Algorithm Theory - Swat 2004 : 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings

3540223398

Summary

Table of Contents

Supplemental Materials

Rewards Program