DecreaseKeys are Expensive for External Memory Priority Queues

Autor: Kasper Green Larsen, Huacheng Yu, Kasper Eenberg

Publikováno v: Eenberg, K, Larsen, K G & Yu, H 2017, DecreaseKeys are expensive for external memory priority queues . in STOC 2017-Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . vol. Part F128415, Association for Computing Machinery, New York, NY, pp. 1081-1093, 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, Canada, 19/06/2017 . https://doi.org/10.1145/3055399.3055437
STOC

One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e9ba578caa17328b64e907faecdc233c
http://arxiv.org/abs/1611.00911