Cache-oblivious priority queue and graph algorithm applications

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 \over B log M/B N \over 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.

Authors

• Lars Arge
• Michael A. Bender
• Erik D. Demaine
• Bryan Holland-Minkley
• J. Ian Munro

Keywords

No keywords are indexed for this paper.