**Reference**:- Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro, “Cache-Oblivious Priority Queue and Graph Algorithm Applications”, in
*Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002)*, Montréal, Québec, Canada, May 19–21, 2002, pages 268–276. **Abstract**:-
In this paper we develop an optimal cache-oblivious priority queue data
structure, supporting insertion, deletion, and deletemin operations in
*O*((1/*B*) log_{M/B}(*N*/*B*)) amortized memory transfers, where*M*and*B*are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure,*M*and*B*are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about*M*and*B*. Priority queues are a critical component in many of the best known external-memory graph algorithms, and using our cache-oblivious priority queue we develop several cache-oblivious graph algorithms. **Length**:- The paper is 9 pages.
**Availability**:- The paper is available in PostScript (245k), gzipped PostScript (93k), and PDF (186k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- BufferTrees_SICOMP (An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms)

See also other papers by Erik Demaine.

Last updated July 21, 2021 by Erik Demaine.