Algorithm Theory - SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings

Front Matter....Pages -
Optimal Exploration of Terrains with Obstacles....Pages 1-12
Reconstructing a Simple Polygon from Its Angles....Pages 13-24
Semidefinite Programming and Approximation Algorithms: A Survey....Pages 25-25
Strictly-Regular Number System and Data Structures....Pages 26-37
An O (log log n )-Competitive Binary Search Tree with Optimal Worst-Case Access Times....Pages 38-49
The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition....Pages 50-61
A Bottom-Up Method and Fast Algorithms for max independent set ....Pages 62-73
Capacitated Domination Faster Than O (2 n )....Pages 74-80
Isomorphism for Graphs of Bounded Feedback Vertex Set Number....Pages 81-92
On Feedback Vertex Set New Measure and New Structures....Pages 93-104
Conflict-Free Coloring Made Stronger....Pages 105-117
Polychromatic Coloring for Half-Planes....Pages 118-126
A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem....Pages 127-138
Minimum and Maximum against k Lies....Pages 139-149
Feasible and Accurate Algorithms for Covering Semidefinite Programs....Pages 150-162
The Quantitative Analysis of User Behavior Online – Data, Models and Algorithms....Pages 163-163
Systems of Linear Equations over $\\mathbb{F}_2$ and Problems Parameterized above Average....Pages 164-175
Capacitated max -Batching with Interval Graph Compatibilities....Pages 176-187
A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs....Pages 188-199
Representing a Functional Curve by Curves with Fewer Peaks....Pages 200-211
Bregman Clustering for Separable Instances....Pages 212-223
Improved Methods For Generating Quasi-gray Codes....Pages 224-235
The MST of Symmetric Disk Graphs Is Light....Pages 236-247
Vector Bin Packing with Multiple-Choice....Pages 248-259
Bin Packing with Fixed Number of Bins Revisited....Pages 260-272
Cops and Robber Game without Recharging....Pages 273-284
Path Schematization for Route Sketches....Pages 285-296
Approximation Algorithms for Free-Label Maximization....Pages 297-308
Phase Transitions in Sampling Algorithms and the Underlying Random Structures....Pages 309-309
Polynomial Kernels for Hard Problems on Disk Graphs....Pages 310-321
Faster Parameterized Algorithms for Minor Containment....Pages 322-333
Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing....Pages 334-345
Dispatching Equal-Length Jobs to Parallel Machines to Maximize Throughput....Pages 346-358
Online Function Tracking with Generalized Penalties....Pages 359-370
Better Bounds on Online Unit Clustering....Pages 371-382
Online Selection of Intervals and t -Intervals....Pages 383-394
Approximating the Maximum 3- and 4-Edge-Colorable Subgraph....Pages 395-407
Improved Algorithm for Degree Bounded Survivable Network Design Problem....Pages 408-419
Minimizing the Diameter of a Network Using Shortcut Edges....Pages 420-431
Back Matter....Pages -