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

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 -