Algorithms are at the heart of every nontrivial computer application, and algorithmics is a
modern and active area of computer science. Every computer scientist and every …

viii Preface reason for this change is that sequential processors have ceased to get
proportional performance improvements from increased circuit complexity. Although the …

We present the software library Stxxl that is an implementation of the C++ standard template
library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel …

This paper defines algorithm engineering as a general methodology for algorithmic
research. The main process in this methodology is a cycle consisting of algorithm design …

Sparse matrices are a key data structure for implementing graph algorithms using linear
algebra. This chapter reviews and evaluates storage formats for sparse matrices and their …

Tries are the fastest tree-based data structures for managing strings in-memory, but are
space-intensive. The burst-trie is almost as fast but reduces space by collapsing trie-chains …

We present improved cache-oblivious data structures and algorithms for breadth-first search
and the single-source shortest path problem on undirected graphs with non-negative edge …

We present a software library Stxxl, that enables practice-oriented experimentation with
huge data sets. Stxxl is an implementation of the C++ standard template library STL for …

Abstract Breadth First Search (BFS) traversal is an archetype for many important graph
problems. However, computing a BFS level decomposition for massive graphs was …

We develop an external memory algorithm for computing minimum spanning trees. The
algorithm is considerably simpler than previously known external memory algorithms for this …