Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings

Front Matter....Pages -
The Online Replacement Path Problem....Pages 1-12
Flip Distance between Triangulations of a Simple Polygon is NP-Complete....Pages 13-24
Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures....Pages 25-36
Computing the Greedy Spanner in Linear Space....Pages 37-48
Friendship and Stable Matching....Pages 49-60
An Optimal and Practical Cache-Oblivious Algorithm for Computing Multiresolution Rasters....Pages 61-72
Logit Dynamics with Concurrent Updates for Local Interaction Games....Pages 73-84
On Resilient Graph Spanners....Pages 85-96
Maximizing Barrier Coverage Lifetime with Mobile Sensors....Pages 97-108
Theory and Implementation of Online Multiselection Algorithms....Pages 109-120
An Implementation of I/O-Efficient Dynamic Breadth-First Search Using Level-Aligned Hierarchical Clustering....Pages 121-132
Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform....Pages 133-144
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement....Pages 145-156
A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree....Pages 157-168
Parallel String Sample Sort....Pages 169-180
Exclusive Graph Searching....Pages 181-192
Largest Chordal and Interval Subgraphs Faster Than 2 n ....Pages 193-204
Revisiting the Problem of Searching on a Line....Pages 205-216
On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity....Pages 217-228
The Encoding Complexity of Two Dimensional Range Minimum Data Structures....Pages 229-240
Computing the Fréchet Distance with a Retractable Leash....Pages 241-252
Vertex Deletion for 3D Delaunay Triangulations....Pages 253-264
Economic 3-Colored Subdivision of Triangulations....Pages 265-276
Limitations of Deterministic Auction Design for Correlated Bidders....Pages 277-288
Connectivity Inference in Mass Spectrometry Based Structure Determination....Pages 289-300
Secluded Connectivity Problems....Pages 301-312
List H-Coloring a Graph by Removing Few Vertices....Pages 313-324
Rumor Spreading in Random Evolving Graphs....Pages 325-336
Dynamic Graphs in the Sliding-Window Model....Pages 337-348
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems....Pages 349-360
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy....Pages 361-372
Labeling Moving Points with a Trade-Off between Label Speed and Label Overlap....Pages 373-384
Inefficiency of Standard Multi-unit Auctions....Pages 385-396
FPTAS for Minimizing Earth Mover’s Distance under Rigid Transformations....Pages 397-408
Maximizing a Submodular Function with Viability Constraints....Pages 409-420
Table Cartograms....Pages 421-432
Network Bargaining with General Capacities....Pages 433-444
Nearly Optimal Private Convolution....Pages 445-456
Tractable Parameterizations for the Minimum Linear Arrangement Problem....Pages 457-468
Compressed Cache-Oblivious String B-tree....Pages 469-480
BICO: BIRCH Meets Coresets for k -Means Clustering....Pages 481-492
Long Circuits and Large Euler Subgraphs....Pages 493-504
Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph....Pages 505-516
Binary Jumbled Pattern Matching on Trees and Tree-Like Structures....Pages 517-528
Kernelization Using Structural Parameters on Sparse Graph Classes....Pages 529-540
On the Computational Complexity of Erdős-Szekeres and Related Problems in ℝ 3 ....Pages 541-552
Encodings for Range Selection and Top- k  Queries....Pages 553-564
Fréchet Queries in Geometric Trees....Pages 565-576
A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs....Pages 577-588
An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions....Pages 589-600
Balls into Bins Made Faster....Pages 601-612
An Alternative Approach to Alternative Routes: HiDAR....Pages 613-624
Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet....Pages 625-636
Better Approximation Algorithms for Technology Diffusion....Pages 637-646
On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility....Pages 647-658
Balanced Neighbor Selection for BitTorrent-Like Networks....Pages 659-670
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs....Pages 671-682
Improved Approximation Algorithms for Projection Games....Pages 683-694
The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology....Pages 695-706
Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections....Pages 707-718
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial....Pages 719-730
Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets....Pages 731-742
Optimal Color Range Reporting in One Dimension....Pages 743-754
Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling....Pages 755-766
Euclidean Greedy Drawings of Trees....Pages 767-778
Sparse Fault-Tolerant BFS Trees....Pages 779-790
On the Most Likely Convex Hull of Uncertain Points....Pages 791-802
Top- k Document Retrieval in External Memory....Pages 803-814
Shell: A Spatial Decomposition Data Structure for 3D Curve Traversal on Many-Core Architectures....Pages 815-826
Back Matter....Pages -