Algorithms and Data Structures. Proceedings, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings : 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings

This book constitutes the refereed proceedings of the 14th Algorithms and Data Structures Symposium, WADS 2015, held in Victoria, BC, Canada, August 2015. The 54 revised full papers presented in this volume were carefully reviewed and selected from 148 submissions. The Algorithms and Data Structures Symposium - WADS (formerly Workshop on Algorithms And Data Structures), which alternates with the Scandinavian Workshop on Algorithm Theory, is intended as a forum for researchers in the area of design and analysis of algorithms and data structures. WADS includes papers presenting original research on algorithms and data structures in all areas, including bioinformatics, combinatorics, computational geometry, databases, graphics, and parallel and distributed computing. Front Matter....Pages I-XIII Contact Graphs of Circular Arcs....Pages 1-13 Contact Representations of Graphs in 3D....Pages 14-27 Minimizing the Aggregate Movements for Interval Coverage....Pages 28-39 Online Bin Packing with Advice of Small Size....Pages 40-53 On the Approximability of Orthogonal Order Preserving Layout Adjustment....Pages 54-65 An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs....Pages 66-78 Generation of Colourings and Distinguishing Colourings of Graphs....Pages 79-90 Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time....Pages 91-102 On Conflict-Free Multi-coloring....Pages 103-114 Semi-dynamic Connectivity in the Plane....Pages 115-126 Interval Selection in the Streaming Model....Pages 127-139 On the Bounded-Hop Range Assignment Problem....Pages 140-151 Greedy Is an Almost Optimal Deque....Pages 152-165 A New Approach for Contact Graph Representations and Its Applications....Pages 166-177 Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm....Pages 178-188 Select with Groups of 3 or 4....Pages 189-199 Approximating Nearest Neighbor Distances....Pages 200-211 Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs....Pages 212-223 On the Complexity of an Unregulated Traffic Crossing....Pages 224-235 Finding Pairwise Intersections Inside a Query Range....Pages 236-248 Cache-Oblivious Iterated Predecessor Queries via Range Coalescing....Pages 249-262 Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing....Pages 263-275 On the Minimum Eccentricity Shortest Path Problem....Pages 276-288 Convex Polygons in Geometric Triangulations....Pages 289-300 Straight-Line Drawability of a Planar Graph Plus an Edge....Pages 301-313 Solving Problems on Graphs of High Rank-Width....Pages 314-326 The Parametric Closure Problem....Pages 327-338 Rooted Cycle Bases....Pages 339-350 On the Chain Pair Simplification Problem....Pages 351-362 Finding Articulation Points of Large Graphs in Linear Time....Pages 363-372 LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design....Pages 373-385 Universal Reconstruction of a String....Pages 386-397 The Complexity of Dominating Set Reconfiguration....Pages 398-409 Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes....Pages 410-421 Competitive Diffusion on Weighted Graphs....Pages 422-433 Sorting and Selection with Equality Comparisons....Pages 434-445 Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs....Pages 446-457 Fast and Simple Connectivity in Graph Timelines....Pages 458-469 Dynamic Set Intersection....Pages 470-481 Time-Space Trade-offs for Triangulations and Voronoi Diagrams....Pages 482-494 A 2k-vertex Kernel for Maximum Internal Spanning Tree....Pages 495-505 Reconfiguration on Sparse Graphs....Pages 506-517 Smoothed Analysis of Local Search Algorithms....Pages 518-527 Optimal Shuffle Code with Permutation Instructions....Pages 528-541 Non-preemptive Scheduling on Machines with Setup Times....Pages 542-553 A Moderately Exponential Time Algorithm for k-IBDD Satisfiability....Pages 554-565 On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids....Pages 566-577 Elastic Geometric Shape Matching for Point Sets under Translations....Pages 578-592 Constant Time Enumeration by Amortization....Pages 593-605 Computing the Center of Uncertain Points on Tree Networks....Pages 606-618 Swapping Colored Tokens on Graphs....Pages 619-628 Positive Semidefinite Zero Forcing: Complexity and Lower Bounds....Pages 629-639 Back Matter....Pages 641-646