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

In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 480-492. Springer Verlag, Berlin, 2004.

Abstract

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 weights. Our results removes the performance gap between the currently best cache-aware algorithms for these problems and their cache-oblivious counterparts. Our shortest-path 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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2004. All rights reserved.

Online version

swat04.pdf (176 Kb)

DOI

10.1007/978-3-540-27810-8_41

Links

BIBTEX entry

@incollection{swat04,
  author = "Gerth Stølting Brodal and Rolf Fagerberg and Ulrich Meyer and Norbert Zeh",
  booktitle = "Proc. 9th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/978-3-540-27810-8_41",
  isbn = "978-3-540-22339-9",
  pages = "480-492",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths",
  volume = "3111",
  year = "2004"
}

Other versions