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 logM/BN \over B) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a mult... View More