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

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