Algorithm Theory – SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006. Proceedings

Raimund Seidel (auth.), Lars Arge, Rusins Freivalds (eds.)354035753X, 9783540357537

This book constitutes the refereed proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, held in Riga, Latvia, in July 2006.

The proceedings includes 36 revised full papers presented together with 3 invited papers, addressing issues of theoretical algorithmics and applications in various fields including graph algorithms, computational geometry, scheduling, approximation algorithms, network algorithms, data storage and manipulation, combinatorics, sorting, searching, online algorithms, optimization, amd more.

---

Table of contents :
Front Matter….Pages –
Top-Down Analysis of Path Compression: Deriving the Inverse-Ackermann Bound Naturally (and Easily)….Pages 1-1
Results and Problems on Self-adjusting Search Trees and Related Data Structures….Pages 2-2
Classic and Quantum Network Coding….Pages 3-4
Multiplexing Packets with Arbitrary Deadlines in Bounded Buffers….Pages 5-16
Scheduling Jobs on Grid Processors….Pages 17-28
Variable Sized Online Interval Coloring with Bandwidth….Pages 29-40
A Simpler Linear-Time Recognition of Circular-Arc Graphs….Pages 41-52
An ${cal O}(n^{2.75})$ Algorithm for Online Topological Ordering….Pages 53-64
Dynamic Matching Markets and Voting Paths….Pages 65-76
Sorting by Merging or Merging by Sorting?….Pages 77-89
Finding the Position of the k -Mismatch and Approximate Tandem Repeats….Pages 90-101
Unbiased Matrix Rounding….Pages 102-112
Online, Non-preemptive Scheduling of Equal-Length Jobs on Two Identical Machines….Pages 113-123
Paging with Request Sets….Pages 124-135
Decentralization and Mechanism Design for Online Machine Scheduling….Pages 136-147
Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes….Pages 148-159
Exact Computation of Maximum Induced Forest….Pages 160-171
Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus….Pages 172-183
On the Approximation Hardness of Some Generalizations of TSP….Pages 184-195
Reoptimization of Minimum and Maximum Traveling Salesman’s Tours….Pages 196-207
The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights….Pages 208-219
On Guarding Rectilinear Domains….Pages 220-231
Approximation Algorithms for the Minimum Convex Partition Problem….Pages 232-241
Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles….Pages 242-254
Simultaneous Embedding with Two Bends per Edge in Polynomial Area….Pages 255-267
Acyclic Orientation of Drawings….Pages 268-279
Improved Algorithms for Quantum Identification of Boolean Oracles….Pages 280-291
Approximability of Minimum AND-Circuits….Pages 292-303
Triangles, 4-Cycles and Parameterized (In-)Tractability….Pages 304-315
Better Approximation Schemes for Disk Graphs….Pages 316-327
An Approximation Algorithm for the Wireless Gathering Problem….Pages 328-338
Minimum Membership Set Covering and the Consecutive Ones Property….Pages 339-350
Approximating Rational Objectives Is as Easy as Approximating Linear Ones….Pages 351-362
In-Place Algorithms for Computing (Layers of) Maxima….Pages 363-374
Largest and Smallest Tours and Convex Hulls for Imprecise Points….Pages 375-387
On Spanners of Geometric Graphs….Pages 388-399
The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems….Pages 400-410
Linear-Time Algorithms for Tree Root Problems….Pages 411-422
Generalized Powers of Graphs and Their Algorithmic Use….Pages 423-434
Back Matter….Pages –