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

This book constitutes the refereed proceedings of the 13th Algorithms and Data Structures Symposium, WADS 2013, held in London, ON, Canada, August 2013. The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 44 revised full papers presented in this volume were carefully reviewed and selected from 139 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

---

This book constitutes the refereed proceedings of the 13th Algorithms and Data Structures Symposium, WADS 2013, held in London, ON, Canada, August 2013. The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 44 revised full papers presented in this volume were carefully reviewed and selected from 139 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.

---

This book constitutes the refereed proceedings of the 13th Algorithms and Data Structures Symposium, WADS 2013, held in London, ON, Canada, August 2013. The Algorithms and Data Structures Symposium - WADS (formerly "Workshop on Algorithms and Data Structures") is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. The 44 revised full papers presented in this volume were carefully reviewed and selected from 139 submissions. The papers present original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing.
Content:
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
Visibility and Ray Shooting Queries in Polygonal Domains....Pages 232-243
Lift-and-Project Methods for Set Cover and Knapsack....Pages 244-255
Blame Trees....Pages 256-267
Plane 3-trees: Embeddability and Approximation....Pages 268-279
A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs....Pages 280-290
Combinatorial Pair Testing: Distinguishing Workers from Slackers....Pages 291-303
Universal Point Sets for Planar Three-Trees....Pages 304-315
Planar Packing of Binary Trees....Pages 316-327
Hierarchies of Predominantly Connected Communities....Pages 328-340
Joint Cache Partition and Job Assignment on Multi-core Processors....Pages 341-352
Finding the Minimum-Weight k-Path....Pages 353-364
Compressed Persistent Index for Efficient Rank/Select Queries....Pages 365-377
Tight Bounds for Low Dimensional Star Stencils in the External Memory Model....Pages 378-389
Neighborhood-Preserving Mapping between Trees....Pages 390-401
Bounding the Running Time of Algorithms for Scheduling and Packing Problems....Pages 402-414
When Is Weighted Satisfiability FPT?....Pages 415-426
Two-Sided Boundary Labeling with Adjacent Sides....Pages 427-438
Optimal Batch Schedules for Parallel Machines....Pages 439-450
Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition....Pages 451-462
Dynamic Planar Point Location with Sub-logarithmic Local Updates....Pages 463-474
Parameterized Enumeration of (Locally-) Optimal Aggregations....Pages 475-486
MapReduce Algorithmics....Pages 487-498
The Greedy Gray Code Algorithm....Pages 499-511
Back Matter....Pages 512-523
....Pages 524-524