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

by Gudmundsson, Joachim

• ISBN13: 9783540699002
• ISBN10: 3540699007
• Format: Paperback
• Copyright: 2008-09-03
• Publisher: Springer-Verlag New York Inc

Summary

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

A Survey of Results for Deletion Channels and Related Synchronization Channels	p. 1
Nash Bargaining Via Flexible Budget Markets (Abstract)	p. 4
Simplified Planar Coresets for Data Streams	p. 5
Uniquely Represented Data Structures for Computational Geometry	p. 17
I/O Efficient Dynamic Data Structures for Longest Prefix Queries	p. 29
Guarding Art Galleries: The Extra Cost for Sculptures Is Linear	p. 41
Vision-Based Pursuit-Evasion in a Grid	p. 53
Angle Optimization in Target Tracking	p. 65
Improved Bounds for Wireless Localization	p. 77
Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem	p. 90
Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint	p. 102
The Maximum Energy-Constrained Dynamic Flow Problem	p. 114
Bounded Unpopularity Matchings	p. 127
Data Structures with Local Update Operations	p. 138
On the Redundancy of Succinct Data Structures	p. 148
Confluently Persistent Tries for Efficient Version Control	p. 160
A Uniform Approach Towards Succinct Representation of Trees	p. 173
An O(n1.75) Algorithm for L(2, 1)-Labeling of Trees	p. 185
Batch Coloring Flat Graphs and Thin	p. 198
Approximating the Interval Constrained Coloring Problem	p. 210
A Path Cover Technique for LCAs in Dags	p. 222
Boundary Labeling with Octilinear Leaders	p. 234
Distributed Disaster Disclosure	p. 246
Reoptimization of Steiner Trees	p. 258
On the Locality of Extracting a 2-Manifold in IR3	p. 270
On Metric Clustering to Minimize the Sum of Radii	p. 282
On Covering Problems of Rado	p. 294
Packing Rectangles into 2OPT Bins Using Rotations	p. 306
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees	p. 319
Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs	p. 331
On a Special Co-cycle Basis of Graphs	p. 343
A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs	p. 355
Spanners of Additively Weighted Point Sets	p. 367
The Kinetic Facility Location Problem	p. 378
Computing the Greedy Spanner in Near-Quadratic Time	p. 390
Parameterized Computational Complexity of Dodgson and Young Elections	p. 402
Online Compression Caching	p. 414
On Trade-Offs in External-Memory Diameter-Approximation	p. 426
Author Index	p. 437
Table of Contents provided by Blackwell. All Rights Reserved.