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

Description

This book constitutes the proceedings of the 12th International Scandinavian Workshop on Algorithm Theory, held in Bergen, Norway in June 2010. 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 -