External memory priority queues with decrease-key and applications to graph algorithms

We present priority queues in the external memory model with block size B and main memory size M that support on N elements, operation Update (a combination of operations Insert and DecreaseKey) in (Formula presented.) amortized I/Os and operations ExtractMin and Delete in (Formula presented.) amortized I/Os, for any real ε ∈ (0, 1), using (Formula presented.) blocks. Previous I/O-efficient priority queues either support these operations in (Formula presented.) amortized I/Os [Kumar and Schwabe, SPDP’96] or support only operations Insert, Delete and ExtractMin in optimal (Formula presented.) amortized I/Os, however without supporting DecreaseKey [Fadel et al. TCS’99]. We also present buffered repository trees that support on a multi-set of N elements, operation Insert in (Formula presented.) I/Os and operation Extract on K extracted elements in (Formula presented.) amortized I/Os, using O (N/B ) blocks. Previous results achieve (Formula presented.) B I/Os and (Formula presented.) I/Os, respectively [Buchsbaum et al. SODA’00]. Our results imply improved (Formula presented.) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs (V, E) with E = Ω (V 1+ε) ,ε > 0 and V = Ω (M), which is equal to the I/O-optimal bound for sorting E values in external memory.SCOPUS: cp.p27th Annual European Symposium on Algorithms, {ESA} 2019, September 9-11, 2019, Munich/Garching, Germany