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

Forfattere

  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Ulrich Meyer
  • Norbert Zeh

DOI:

https://doi.org/10.7146/brics.v11i2.21827

Resumé

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.

Downloads

Publiceret

2004-02-11

Citation/Eksport

Brodal, G. S., Fagerberg, R., Meyer, U., & Zeh, N. (2004). Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. BRICS Report Series, 11(2). https://doi.org/10.7146/brics.v11i2.21827