Algorithms and Data Structures

Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings (Lecture Notes in … Computer Science and General Issues)

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.

Table of Contents

Chapter 1. On Maximum Weight Objects Decomposable into Based Rectilinear Convex Objects
Chapter 2. Bundling Three Convex Polygons to Minimize Area or Perimeter
Chapter 3. Smart-Grid Electricity Allocation via Strip Packing with Slicing
Chapter 4. On (Dynamic) Range Minimum Queries in External Memory
Chapter 5. Distance-Sensitive Planar Point Location
Chapter 6. Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
Chapter 7. Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
Chapter 8. Socially Stable Matchings in the Hospitals/Residents Problem
Chapter 9. Parameterized Complexity of 1-Planarity
Chapter 10. On the Stretch Factor of the Theta-4 Graph
Chapter 11. Better Space Bounds for Parameterized Range Majority and Minority
Chapter 12. Online Control Message Aggregation in Chain Networks
Chapter 13. Fingerprints in Compressed Strings
Chapter 14. Beacon-Based Algorithms for Geometric Routing
Chapter 15. Interval Selection with Machine-Dependent Intervals
Chapter 16. On the Spanning Ratio of Theta-Graphs
Chapter 17. Relative Interval Analysis of Paging Algorithms on Access Graphs
Chapter 18. On Explaining Integer Vectors by Few Homogenous Segments
Chapter 19. Trajectory Grouping Structure
Chapter 20. The Art of Shaving Logs
Chapter 21. TREEWIDTH and PATHWIDTH Parameterized by the Vertex Cover Number
Chapter 22. Visibility and Ray Shooting Queries in Polygonal Domains
Chapter 23. Lift-and-Project Methods for Set Cover and Knapsack
Chapter 24. Optimal Time-Convex Hull under the Lp Metrics
Chapter 25. Blame Trees
Chapter 26. Plane 3-trees: Embeddability and Approximation
Chapter 27. A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs
Chapter 28. Combinatorial Pair Testing: Distinguishing Workers from Slackers
Chapter 29. Approximation Algorithms for B1-EPG Graphs
Chapter 30. Universal Point Sets for Planar Three-Trees
Chapter 31. Planar Packing of Binary Trees
Chapter 32. Hierarchies of Predominantly Connected Communities
Chapter 33. Joint Cache Partition and Job Assignment on Multi-core Processors
Chapter 34. Finding the Minimum-Weight k-Path
Chapter 35. Compressed Persistent Index for Efficient Rank/Select Queries
Chapter 36. Tight Bounds for Low Dimensional Star Stencils in the External Memory Model
Chapter 37. Neighborhood-Preserving Mapping between Trees
Chapter 38. Bounding the Running Time of Algorithms for Scheduling and Packing Problems
Chapter 39. When Is Weighted Satisfiability FPT?
Chapter 40. Two-Sided Boundary Labeling with Adjacent Sides
Chapter 41. Optimal Batch Schedules for Parallel Machines
Chapter 42. Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition
Chapter 43. Dynamic Planar Point Location with Sub-logarithmic Local Updates
Chapter 44. Parameterized Enumeration of (Locally-) Optimal Aggregations
Chapter 45. MapReduce Algorithmics
Chapter 46. The Greedy Gray Code Algorithm