Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

Gerth Stølting Brodal
Rolf Fagerberg
Ulrich Meyer
Norbert Zeh

February 2004

Abstract:

We present improved cache-oblivious data structures and algorithms for breadth-first search (BFS) on undirected graphs and the single-source shortest path (SSSP) problem on undirected graphs with non-negative edge weights. For the SSSP problem, our result closes the performance gap between the currently best cache-aware algorithm and the cache-oblivious counterpart. Our cache-oblivious SSSP-algorithm takes nearly full advantage of block transfers for dense graphs. The algorithm relies on a new data structure, called bucket heap, which is the first cache-oblivious priority queue to efficiently support a weak DECREASEKEY operation. For the BFS problem, we reduce the number of I/Os for sparse graphs by a factor of nearly $\sqrt{B}$, where $B$ is the cache-block size, nearly closing the performance gap between the currently best cache-aware and cache-oblivious algorithms

Available as PostScript, PDF.

Last modified: 2004-02-16 by webmaster.