×

zbMATH — the first resource for mathematics

A priority queue in which initialization and queue operations take 0(log log D) time. (English) Zbl 0522.68039

MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60K25 Queueing theory (aspects of probability theory)
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley (1974) · Zbl 0326.68005
[2] M. R. Brown. Implementation and analysis of binomial queue algorithms,SIAM J. Comput. 7, 298–319 (1978) · Zbl 0379.68023 · doi:10.1137/0207026
[3] C. A. Crane. Linear lists and priority queues as balanced binary trees, (Ph.D. Thesis)STAN-CS-72-259, Computer Science Department. Stanford University (February 1972)
[4] D. B. Johnson. Efficient special purpose priority queues,Proc. 15th Annual Allerton Conference on Communication, Control, andComputing. Department of Electrical Engineering and the Coordinated Science Laboratory, University of Illinois, 1–7 (1977)
[5] D. B. Johnson. Efficient algorithms for shortest paths in sparse networks,J. ACM 24, 1–13 (1977) · Zbl 0343.68028 · doi:10.1145/321992.321993
[6] D. B. Johnson. Priority queues with update and finding minimum spanning trees,Information Processing Letters 4, 53–57 (1975) · Zbl 0318.68032 · doi:10.1016/0020-0190(75)90001-0
[7] A. Jonassen and O.-J. Dahl. Analysis of an algorithm for priority queue administration,BIT 15, 409–422 (1975) · Zbl 0324.68021 · doi:10.1007/BF01931680
[8] D. E. Knuth.The Art of Computer Programming, Volume 3/Sorting and Searching. Addison-Wesley (1973) · Zbl 0302.68010
[9] D. E. Knuth.Notes on the van Emde Boas construction of priority deques: An instructive use of recursion (unpublished notes March 1977)
[10] P. Van Emde Boas. Preserving order in a forest in less than logarithmic time,Proc. Sixteenth IEEE Conference on Foundations of Computer Science. Berkeley, California, 75–84 (1975) · Zbl 0364.68053
[11] P. Van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue,Mathematical Systems Theory 10, 99–127 (1977) · Zbl 0363.60104
[12] P. Van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space,Information Processing Letters 6, 80–82 (1977) · Zbl 0364.68053 · doi:10.1016/0020-0190(77)90031-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.