A priority queue in which initialization and queue operations takeO(loglogD) time

DOI10.1007/BF01786986MaRDI QIDQ3673101zbMATHOpenAlexWikidataFDO

Authors Donald B. Johnson

Publication date 1982

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01786986

zbMATH Keywords

data structuretime complexitybinary treepriority queue

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Data structures (68P05)

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Analysis of an algorithm for priority queue administration
• Design and implementation of an efficient priority queue
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Implementation and Analysis of Binomial Queue Algorithms
• Preserving order in a forest in less than logarithmic time and linear space
• Priority queues with update and finding minimum spanning trees

Cited in

(26)

• Scanline algorithms on a grid
• An O(m log log D) algorithm for shortest paths
• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• Compact recognizers of episode sequences
• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• Sorting by bounded block-moves
• Computing the agreement of trees with bounded degrees
• New clique and independent set algorithms for circle graphs
• On building the transitive reduction of a two-dimensional poset
• Two- and three- dimensional point location in rectangular subdivisions
• Fast local searches and updates in bounded universes
• A faster polynomial algorithm for the constrained maximum flow problem
• Range-restricted mergeable priority queues
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Sorting helps for Voronoi diagrams
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Finding the k Shortest Paths
• EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING
• The k most vital arcs in the shortest path problem
• New trie data structures which support very fast search operations
• Chaining algorithms for multiple genome comparison
• Dynamic programming with convexity, concavity and sparsity
• Routing a vehicle of capacity greater than one
• A double scaling algorithm for the constrained maximum flow problem
• A history of distribution-sensitive data structures
• On graphs preserving rectilinear shortest paths in the presence of obstacles

This page was built for publication: A priority queue in which initialization and queue operations takeO(loglogD) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3673101)