Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings

Front Matter....Pages -
On Maximum Weight Objects Decomposable into Based Rectilinear Convex Objects....Pages 1-12
Bundling Three Convex Polygons to Minimize Area or Perimeter....Pages 13-24
Smart-Grid Electricity Allocation via Strip Packing with Slicing....Pages 25-36
On (Dynamic) Range Minimum Queries in External Memory....Pages 37-48
Distance-Sensitive Planar Point Location....Pages 49-60
Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems....Pages 61-72
Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles....Pages 73-84
Socially Stable Matchings in the Hospitals/Residents Problem....Pages 85-96
Parameterized Complexity of 1-Planarity....Pages 97-108
On the Stretch Factor of the Theta-4 Graph....Pages 109-120
Better Space Bounds for Parameterized Range Majority and Minority....Pages 121-132
Online Control Message Aggregation in Chain Networks....Pages 133-145
Fingerprints in Compressed Strings....Pages 146-157
Beacon-Based Algorithms for Geometric Routing....Pages 158-169
Interval Selection with Machine-Dependent Intervals....Pages 170-181
On the Spanning Ratio of Theta-Graphs....Pages 182-194
Relative Interval Analysis of Paging Algorithms on Access Graphs....Pages 195-206
On Explaining Integer Vectors by Few Homogenous Segments....Pages 207-218
Trajectory Grouping Structure....Pages 219-230
The Art of Shaving Logs....Pages 231-231
 Treewidth and Pathwidth Parameterized by the Vertex Cover Number....Pages 232-243
Visibility and Ray Shooting Queries in Polygonal Domains....Pages 244-255
Lift-and-Project Methods for Set Cover and Knapsack....Pages 256-267
Optimal Time-Convex Hull under the L p Metrics....Pages 268-279
Blame Trees....Pages 280-290
Plane 3-trees: Embeddability and Approximation....Pages 291-303
A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs....Pages 304-315
Combinatorial Pair Testing: Distinguishing Workers from Slackers....Pages 316-327
Approximation Algorithms for B 1 -EPG Graphs....Pages 328-340
Universal Point Sets for Planar Three-Trees....Pages 341-352
Planar Packing of Binary Trees....Pages 353-364
Hierarchies of Predominantly Connected Communities....Pages 365-377
Joint Cache Partition and Job Assignment on Multi-core Processors....Pages 378-389
Finding the Minimum-Weight k -Path....Pages 390-401
Compressed Persistent Index for Efficient Rank/Select Queries....Pages 402-414
Tight Bounds for Low Dimensional Star Stencils in the External Memory Model....Pages 415-426
Neighborhood-Preserving Mapping between Trees....Pages 427-438
Bounding the Running Time of Algorithms for Scheduling and Packing Problems....Pages 439-450
When Is Weighted Satisfiability FPT?....Pages 451-462
Two-Sided Boundary Labeling with Adjacent Sides....Pages 463-474
Optimal Batch Schedules for Parallel Machines....Pages 475-486
Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition....Pages 487-498
Dynamic Planar Point Location with Sub-logarithmic Local Updates....Pages 499-511
Parameterized Enumeration of (Locally-) Optimal Aggregations....Pages 512-523
MapReduce Algorithmics....Pages 524-524
The Greedy Gray Code Algorithm....Pages 525-536
Back Matter....Pages -