Algorithm Theory – SWAT 2012: 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings

Front Matter....Pages -
 α -Visibility....Pages 1-12
Partial Matching between Surfaces Using Fréchet Distance....Pages 13-23
A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares....Pages 24-35
Watchman Routes for Lines and Segments....Pages 36-47
Kinetic Pie Delaunay Graph and Its Applications....Pages 48-58
Higher Order City Voronoi Diagrams....Pages 59-70
On Minimum Sum of Radii and Diameters Clustering....Pages 71-82
A Simple Framework for the Generalized Nearest Neighbor Problem....Pages 83-94
Deterministic Parameterized Connected Vertex Cover....Pages 95-106
Faster Parameterized Algorithms for Deletion to Split Graphs....Pages 107-118
A Single-Exponential FPT Algorithm for the K 4 -Minor Cover Problem....Pages 119-130
An O ( n 3 loglog n /log 2 n ) Time Algorithm for All Pairs Shortest Paths....Pages 131-141
Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths....Pages 142-152
Induced Disjoint Paths in AT-Free Graphs....Pages 153-164
Effective Computation of Immersion Obstructions for Unions of Graph Classes....Pages 165-176
Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain....Pages 177-188
Annotating Simplices with a Homology Basis and Its Applications....Pages 189-200
Do Directional Antennas Facilitate in Reducing Interferences?....Pages 201-212
Minimum Convex Partitions and Maximum Empty Polytopes....Pages 213-224
A Probabilistic Analysis of Christofides’ Algorithm....Pages 225-236
New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem....Pages 237-248
Non-preemptive Speed Scaling....Pages 249-260
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs....Pages 261-270
Sorted Range Reporting....Pages 271-282
String Indexing for Patterns with Wildcards....Pages 283-294
Linear-Space Data Structures for Range Minority Query in Arrays....Pages 295-306
Asynchronous Rumor Spreading in Preferential Attachment Graphs....Pages 307-315
Connectivity Oracles for Planar Graphs....Pages 316-327
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis....Pages 328-339
Competitive Analysis of Maintaining Frequent Items of a Stream....Pages 340-351
Kernel Bounds for Structural Parameterizations of Pathwidth....Pages 352-363
Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs....Pages 364-375
Testing Formula Satisfaction....Pages 376-387
Reconstructing Strings from Substrings with Quantum Queries....Pages 388-397
Back Matter....Pages -