Algorithm Engineering

1. Front Matter

   Pages I-X

   PDF

2. Compact DFA Representation for Fast Regular Expression Search

   • Gonzalo Navarro, Mathieu Raffinot

   Pages 1-13

3. The Max-Shift Algorithm for Approximate String Matching

   • Costas S. Iliopoulos, Laurent Mouchard, Yoan J. Pinzon

   Pages 13-25

4. Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance

   • Gianfranco Bilardi, Paolo D’Alberto, Alex Nicolau

   Pages 26-38

5. Experiences with the Design and Implementation of Space-Efficient Deques

   • Jyrki Katajainen, Bjarke Buur Mortensen

   Pages 39-50

6. Designing and Implementing a General Purpose Halfedge Data Structure

   • Hervé Brönnimann

   Pages 51-66

7. Optimised Predecessor Data Structures for Internal Memory

   • Naila Rahman, Richard Cole, Rajeev Raman

   Pages 67-78

8. An Adaptable and Extensible Geometry Kernel

   • Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, Michael Seel

   Pages 79-90

9. Efficient Resource Allocation with Noisy Functions

   • Arne Andersson, Per Carlsson, Fredrik Ygge

   Pages 91-105

10. Improving the Efficiency of Branch and Bound Algorithms for the Simple Plant Location Problem

    • Boris Goldengorin, Diptesh Ghosh, Gerard Sierksma

    Pages 106-117

11. Exploiting Partial Knowledge of Satisfying Assignments

    • Kazuo Iwama, Suguru Tamaki

    Pages 118-128

12. Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture

    • David A. Bader, Ajith K. Illendula, Bernard M. E. Moret, Nina R. Weisse-Bernstein

    Pages 129-144

13. An Experimental Study of Data Migration Algorithms

    • Eric Anderson, Joe Hall, Jason Hartline, Michael Hobbs, Anna R. Karlin, Jared Saia et al.

    Pages 145-158

14. An Experimental Study of Basic Communication Protocols in Ad-hoc Mobile Networks

    • Ioannis Chatzigiannakis, Sotiris Nikoletseas, Nearchos Paspallis, Paul Spirakis, Christos Zaroliagis

    Pages 159-171

15. Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry

    • Chris Barrett, Doug Cook, Gregory Hicks, Vance Faber, Achla Marathe, Madhav Marathe et al.

    Pages 172-184

16. Pareto Shortest Paths is Often Feasible in Practice

    • Matthias Müller-Hannemann, Karsten Weihe

    Pages 185-197

17. Back Matter

    Pages 199-199

    PDF

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.

• algorithm engineering
• algorithms
• data structures
• discrete algorithms
• experimental algorithmics
• network algorithms
• optimization algorithms
• scheduling
• search algorithms
• shortest paths algorithms
• string matching
• algorithm analysis and problem complexity

• Department of Computer Science, University of Aarhus, BRICS, Åarhus, Denmark

  Gerth Stølting Brodal

• Dipartimento di Ingegneria Elettrica, Universitá dell’Aquila, L’Aquila, Italy

  Daniele Frigioni

• Dipartimento di Informatica e Sistemistica, Universitá di Roma “La Sapienza”, Roma, Italy

  Alberto Marchetti-Spaccamela

Policies and ethics