2026-08-16T13:17:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11181 2024-03-06T10:47:39Z ddc:004 open_access

External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms Iacono, John Jacob, Riko Tsakalidis, Konstantinos priority queues external memory graph algorithms shortest paths depth-first search breadth-first search 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 O(1/Blog_{M/B} N/B) amortized I/Os and operations ExtractMin and Delete in O(ceil[(M^epsilon)/B log_{M/B} N/B] log_{M/B} N/B) amortized I/Os, for any real epsilon in (0,1), using O(N/Blog_{M/B} N/B) blocks. Previous I/O-efficient priority queues either support these operations in O(1/Blog_2 N/B) amortized I/Os [Kumar and Schwabe, SPDP '96] or support only operations Insert, Delete and ExtractMin in optimal O(1/Blog_{M/B} N/B) 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 O(1/Blog_M/B N/B) I/Os and operation Extract on K extracted elements in O(M^{epsilon} log_M/B N/B + K/B) amortized I/Os, using O(N/B) blocks. Previous results achieve O(1/Blog_2 N/B) I/Os and O(log_2 N/B + K/B) I/Os, respectively [Buchsbaum et al., SODA '00]. Our results imply improved O(E/Blog_{M/B} E/B) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs (V,E) with E = Omega (V^(1+epsilon)), epsilon > 0 and V = Omega (M), which is equal to the I/O-optimal bound for sorting E values in external memory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Iacono and Riko Jacob and Konstantinos Tsakalidis 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.60 urn:nbn:de:0030-drops-111817 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.60 eng https://creativecommons.org/licenses/by/3.0/legalcode