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

Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh

Technical Report, BRICS-RS-04-2, BRICS, Department of Computer Science, Aarhus University, 19 pages, January 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.

Copyright notice

Copyright © 2004, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-04-2.pdf (220 Kb)

BIBT_EX entry

@techreport{brics-rs-04-2,
  author = "Gerth Stølting Brodal and Rolf Fagerberg and Ulrich Meyer and Norbert Zeh",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "January",
  number = "BRICS-RS-04-2",
  pages = "19",
  title = "Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths",
  year = "2004"
}