Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings

Front Matter....Pages -
Losing Weight by Gaining Edges....Pages 1-12
Optimal Coordination Mechanisms for Multi-job Scheduling Games....Pages 13-24
Theory and Practice of Chunked Sequences....Pages 25-36
Convex Hulls under Uncertainty....Pages 37-48
The Space-Stretch-Time Tradeoff in Distance Oracles....Pages 49-60
Distribution-Sensitive Construction of the Greedy Spanner....Pages 61-73
Recognizing Shrinkable Complexes Is NP-Complete....Pages 74-86
Improved Approximation Algorithms for Box Contact Representations....Pages 87-99
Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms....Pages 100-111
The Batched Predecessor Problem in External Memory....Pages 112-124
Polynomial Decompositions in Polynomial Time....Pages 125-136
Fault-Tolerant Approximate Shortest-Path Trees....Pages 137-148
Fast Witness Extraction Using a Decision Oracle....Pages 149-160
Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model....Pages 161-172
A Subexponential Parameterized Algorithm for Proper Interval Completion....Pages 173-184
Computing Persistent Homology with Various Coefficient Fields in a Single Pass....Pages 185-196
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time....Pages 197-208
Competitive Algorithms for Restricted Caching and Matroid Caching....Pages 209-221
Improved Algorithms for Resource Allocation under Varying Capacity....Pages 222-234
Nearly Tight Approximability Results for Minimum Biclique Cover and Partition....Pages 235-246
Succinct Indices for Path Minimum, with Applications to Path Reporting....Pages 247-259
Online Bipartite Matching with Decomposable Weights....Pages 260-271
A Faster Algorithm for Computing Straight Skeletons....Pages 272-283
Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem....Pages 284-295
Cache-Oblivious Persistence....Pages 296-308
Lightweight Approximate Selection....Pages 309-320
Robust Distance Queries on Massive Networks....Pages 321-333
A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth....Pages 334-345
Large Independent Sets in Triangle-Free Planar Graphs....Pages 346-357
GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem....Pages 358-370
Switching Colouring of G ( n , d / n ) for Sampling up to Gibbs Uniqueness Threshold....Pages 371-381
From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?....Pages 382-393
Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs....Pages 394-405
Bicriteria Data Compression: Efficient and Usable....Pages 406-417
Amortized $\\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs....Pages 418-429
LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs....Pages 430-442
Representative Sets of Product Families....Pages 443-454
Weighted Ancestors in Suffix Trees....Pages 455-466
Improved Practical Matrix Sketching with Guarantees....Pages 467-479
Computing Regions Decomposable into m Stars....Pages 480-491
The Parameterized Complexity of Graph Cyclability....Pages 492-504
Dimension Reduction via Colour Refinement....Pages 505-516
How Experts Can Solve LPs Online....Pages 517-529
Parameterized Complexity of the k -Arc Chinese Postman Problem....Pages 530-541
Approximating the Maximum Overlap of Polygons under Translation....Pages 542-553
Ordering without Forbidden Patterns....Pages 554-565
Halving Balls in Deterministic Linear Time....Pages 566-578
Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes....Pages 579-591
Optimal Parallel Quantum Query Algorithms....Pages 592-604
Sublinear Space Algorithms for the Longest Common Substring Problem....Pages 605-617
Nested Set Union....Pages 618-629
Improved Explicit Data Structures in the Bitprobe Model....Pages 630-641
Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees....Pages 642-653
FPTAS for Counting Weighted Edge Covers....Pages 654-665
Solving Multicut Faster Than 2 n ....Pages 666-676
Tight Bounds for Active Self-assembly Using an Insertion Primitive....Pages 677-688
Trace Reconstruction Revisited....Pages 689-700
PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies....Pages 701-712
Polynomial-Time Approximation Schemes for Circle Packing Problems....Pages 713-724
Document Retrieval on Repetitive Collections....Pages 725-736
An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs....Pages 737-749
The Input/Output Complexity of Sparse Matrix Multiplication....Pages 750-761
Faster FPTASes for Counting and Random Generation of Knapsack Solutions....Pages 762-773
Improved Guarantees for Tree Cut Sparsifiers....Pages 774-785
Representative Families: A Unified Tradeoff-Based Approach....Pages 786-797
A Branch and Price Procedure for the Container Premarshalling Problem....Pages 798-809
Space-Efficient Randomized Algorithms for K-SUM....Pages 810-829
Equivalence between Priority Queues and Sorting in External Memory....Pages 830-841
Amortized Bounds for Dynamic Orthogonal Range Reporting....Pages 842-856
Back Matter....Pages -