Algorithm Engineering: 5th International Workshop, WAE 2001 Århus, Denmark, August 28–31, 2001 Proceedings

Gonzalo Navarro, Mathieu Raffinot (auth.), Gerth Stølting Brodal, Daniele Frigioni, Alberto Marchetti-Spaccamela (eds.)3540425004, 9783540425007

This book constitutes the refereed proceedings of the 5th Workshop on Algorithm Engineering, WAE 2001, held in Aarhus, Denmark, in August 2001. The 15 revised full papers presented were carefully reviewed and selected from 25 submissions. Among the topics addressed are implementation, experimental testing, and fine-tuning of discrete algorithms; novel use of discrete algorithms in other disciplines; empirical research on algorithms and data structures; and methodological issues regarding the process of converting user requirements into efficient algorithmic solutions and implemenations.

---

Table of contents :
Compact DFA Representation for Fast Regular Expression Search….Pages 1-13
The Max-Shift Algorithm for Approximate String Matching….Pages 13-25
Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance….Pages 26-38
Experiences with the Design and Implementation of Space-Efficient Deques….Pages 39-50
Designing and Implementing a General Purpose Halfedge Data Structure….Pages 51-66
Optimised Predecessor Data Structures for Internal Memory….Pages 67-78
An Adaptable and Extensible Geometry Kernel….Pages 79-90
Efficient Resource Allocation with Noisy Functions….Pages 91-105
Improving the Efficiency of Branch and Bound Algorithms for the Simple Plant Location Problem….Pages 106-117
Exploiting Partial Knowledge of Satisfying Assignments….Pages 118-128
Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture….Pages 129-144
An Experimental Study of Data Migration Algorithms….Pages 145-158
An Experimental Study of Basic Communication Protocols in Ad-hoc Mobile Networks….Pages 159-171
Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry….Pages 172-184
Pareto Shortest Paths is Often Feasible in Practice….Pages 185-197