Algorithm Theory – SWAT 2008: 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008. Proceedings

Michael Mitzenmacher (auth.), Joachim Gudmundsson (eds.)3540699007, 9783540699002

This book constitutes the refereed proceedings of the 11th Scandinavian Workshop on Algorithm Theory, SWAT 2008, held in Gothenborg, Sweden, in July 2008.

The 36 revised full papers presented together with 2 invited lectures were carefully reviewed and selected from 111 submissions. Papers were solicited for original research on algorithms and data structures in all areas, including but not limited to: approximation algorithms, computational biology, computational geometry, distributed algorithms, external-memory algorithms, graph algorithms, online algorithms, optimization algorithms, parallel algorithms, randomized algorithms, string algorithms and algorithmic game theory.

---

Table of contents :
Front Matter….Pages –
A Survey of Results for Deletion Channels and Related Synchronization Channels….Pages 1-3
Nash Bargaining Via Flexible Budget Markets….Pages 4-4
Simplified Planar Coresets for Data Streams….Pages 5-16
Uniquely Represented Data Structures for Computational Geometry….Pages 17-28
I/O Efficient Dynamic Data Structures for Longest Prefix Queries….Pages 29-40
Guarding Art Galleries: The Extra Cost for Sculptures Is Linear….Pages 41-52
Vision-Based Pursuit-Evasion in a Grid….Pages 53-64
Angle Optimization in Target Tracking….Pages 65-76
Improved Bounds for Wireless Localization….Pages 77-89
Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem….Pages 90-101
Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint….Pages 102-113
The Maximum Energy-Constrained Dynamic Flow Problem….Pages 114-126
Bounded Unpopularity Matchings….Pages 127-137
Data Structures with Local Update Operations….Pages 138-147
On the Redundancy of Succinct Data Structures….Pages 148-159
Confluently Persistent Tries for Efficient Version Control….Pages 160-172
A Uniform Approach Towards Succinct Representation of Trees….Pages 173-184
An $mbox{O}(n^{1.75})$ Algorithm for L (2,1)-Labeling of Trees….Pages 185-197
Batch Coloring Flat Graphs and Thin….Pages 198-209
Approximating the Interval Constrained Coloring Problem….Pages 210-221
A Path Cover Technique for LCAs in Dags….Pages 222-233
Boundary Labeling with Octilinear Leaders….Pages 234-245
Distributed Disaster Disclosure….Pages 246-257
Reoptimization of Steiner Trees….Pages 258-269
On the Locality of Extracting a 2-Manifold in ….Pages 270-281
On Metric Clustering to Minimize the Sum of Radii….Pages 282-293
On Covering Problems of Rado….Pages 294-305
Packing Rectangles into 2OPT Bins Using Rotations….Pages 306-318
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees….Pages 319-330
Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs….Pages 331-342
On a Special Co-cycle Basis of Graphs….Pages 343-354
A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs….Pages 355-366
Spanners of Additively Weighted Point Sets….Pages 367-377
The Kinetic Facility Location Problem….Pages 378-389
Computing the Greedy Spanner in Near-Quadratic Time….Pages 390-401
Parameterized Computational Complexity of Dodgson and Young Elections….Pages 402-413
Online Compression Caching….Pages 414-425
On Trade-Offs in External-Memory Diameter-Approximation….Pages 426-436
Back Matter….Pages –