Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (Proceedings in Applied Mathematics)

PROCEEDINGS OF THE NINTH WORKSHOP ON ALGORITHM ENGINEERING AND EXPERIMENTS AND THE FOURTH WORKSHOP ON ANALYTIC ALGORITHMICS AND COMBINATORICS......Page 1
CONTENTS......Page 6
ALENEX WORKSHOP PREFACE......Page 7
ANALCO WORKSHOP PREFACE......Page 9
Workshop on Algorithm Engineering and Experiments......Page 10
Improved external memory BFS implementations......Page 12
Computing Visibility on Terrains in External Memory......Page 22
An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances......Page 32
Computing Many-to-Many Shortest Paths Using Highway Hierarchies*......Page 45
In Transit to Constant Time Shortest-Path Queries in Road Networks*......Page 55
Practical Entropy-Compressed Rank/Select Dictionary......Page 69
Intersection in Integer Inverted Indices......Page 80
Faster Filters for Approximate String Matching......Page 93
Algorithms to Take Advantage of Hardware Prefetching......Page 100
Linearization: Locally Self-Stabilizing Sorting in Graphs......Page 108
Maximizing Throughput in Minimum Rounds in an Application-Level Relay Service*......Page 118
Locating Guards for Visibility Coverage of Polygons*......Page 129
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs......Page 144
ScrewBox: a Randomized Certifying Graph-Non-Isomorphism Algorithm......Page 159
0/1 vertex and facet enumeration with BDDs*......Page 167
Workshop on Analytic Algorithmics and Combinatorics......Page 176
Fast Sorting and Pattern-Avoiding Permutations......Page 178
Analysis of insertion costs in priority trees......Page 184
The Average Profile of Suffix Trees......Page 192
On the average cost of insertions on random relaxed K-d trees*......Page 203
Boltzmann Sampling of Unlabelled Structures......Page 210
LRU Caching with Moderately Heavy Request Distributions......Page 221
Estimating the number of Active Flows in a Data Stream over a Sliding Window......Page 232
A CHARACTERIZATION OF THE DEGREE SEQUENCES OF 2-TREES......Page 241
The Asymptotic Number of Spanning Trees in Circulant Graphs......Page 251
Smoothed Analysis of Probabilistic Roadmaps......Page 259
On the reduction of a random basis......Page 274
Analysis of fast versions of the Euclid Algorithm......Page 280
ALENEX/ANALCO AUTHOR INDEX......Page 296