Cache-oblivious priority queue and graph algorithm applications
| Autor: | Erik D. Demaine, Bryan Holland-Minkley, Lars Arge, J. Ian Munro, Michael A. Bender |
|---|---|
| Rok vydání: | 2002 |
| Předmět: | |
| Zdroj: | STOC Arge, L A, Bender, M A, Demaine, E D, Holland-Minkley, B & Munro, J I 2002, Cache-oblivious priority queue and graph algorithm applications . in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing . Association for Computing Machinery, pp. 268-276, Annual ACM Symposium on Theory of Computing, Montreal, Canada, 17/12/2010 . https://doi.org/10.1145/509907.509950 Arge, L, Bender, M A, Demaine, E D & Munro, J I 2007, ' Cache-Oblivious Priority Queue and Graph Algorithm Applications ', S I A M Journal on Computing, vol. 36, no. 6, pp. 1672-1695 . https://doi.org/10.1145/509907.509950 |
| DOI: | 10.1145/509907.509950 |
| Popis: | (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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|