Algorithm Engineering: 3rd International Workshop, WAE’99 London, UK, July 19–21, 1999 Proceedings

Andrew V. Goldberg (auth.), Jeffrey S. Vitter, Christos D. Zaroliagis (eds.)3540664270, 9783540664277

This book constitutes the refereed proceedings of the Third International Workshop on Algorithm Engineering, WAE’99, held in London, UK in July 1999.
The 24 revised full papers presented were carefully reviewed and selected from a total of 46 submissions. The papers present original research results in all aspects of algorithm engineering including implementation, experimental testing, fine-tuning of discrete algorithms, development of repositories of software, methodological issues such as standards for empirical research on algorithms and data structures, and issues in the process of converting user requirements into efficient algorithmic solutions and implementations.

---

Table of contents :
Selecting Problems for Algorithm Evaluation….Pages 1-11
BSP Algorithms — “Write Once, Run Anywhere”….Pages 12-13
Ten Years of LEDA: Some Thoughts….Pages 14-14
Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison….Pages 15-29
Efficient Implementation of Lazy Suffix Trees….Pages 30-42
Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism….Pages 43-59
Finding Minimum Congestion Spanning Trees….Pages 60-71
Evaluation of an Algorithm for the Transversal Hypergraph Problem….Pages 72-84
Construction Heuristics and Domination Analysis for the Asymmetric TSP….Pages 85-94
Counting in Mobile Networks: Theory and Experimentation….Pages 95-109
Dijkstra’s Algorithm On-Line: An Empirical Case Study from Public Railroad Transport….Pages 110-123
Implementation and Experimental Evaluation of Graph Connectivity Algorithms Using LEDA….Pages 124-138
On-Line Zone Construction in Arrangements of Lines in the Plane….Pages 139-153
The Design and Implementation of Planar Maps in CGAL….Pages 154-168
An Easy to Use Implementation of Linear Perturbations within C upgal ….Pages 169-182
Analysing Cache Effects in Distribution Sorting….Pages 183-197
Fast Regular Expression Search….Pages 198-212
An Experimental Evaluation of Hybrid Data Structures for Searching….Pages 213-227
LEDA-SM: Extending LEDA to Secondary Memory….Pages 228-242
A Priority Queue Transform….Pages 243-257
Implementation Issues and Experimental Study of a Wavelength Routing Algorithm for Irregular All-Optical Networks….Pages 258-270
Estimating Large Distances in Phylogenetic Reconstruction….Pages 271-285
The Performance of Concurrent Red-Black Tree Algorithms….Pages 286-300
Performance Engineering Case Study: Heap Construction….Pages 301-315
A Fast and Simple Local Search for Graph Coloring….Pages 316-329
BALL: Biochemical Algorithms Library….Pages 330-344
An Experimental Study of Priority Queues in External Memory….Pages 345-359