A priority queue in which initialization and queue operations takeO(loglogD) time
DOI10.1007/BF01786986zbMATH Open0522.68039OpenAlexW1977421134WikidataQ56078244 ScholiaQ56078244MaRDI QIDQ3673101FDOQ3673101
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Preserving order in a forest in less than logarithmic time and linear space
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Design and implementation of an efficient priority queue
- Implementation and Analysis of Binomial Queue Algorithms
- Analysis of an algorithm for priority queue administration
- Priority queues with update and finding minimum spanning trees
Cited In (27)
- Bounded ordered dictionaries in O(log log N) time and O(n) space
- Range-restricted mergeable priority queues
- Fast local searches and updates in bounded universes
- Two- and three- dimensional point location in rectangular subdivisions
- Routing a vehicle of capacity greater than one
- New clique and independent set algorithms for circle graphs
- The k most vital arcs in the shortest path problem
- On building the transitive reduction of a two-dimensional poset
- A faster polynomial algorithm for the constrained maximum flow problem
- Sorting helps for Voronoi diagrams
- A double scaling algorithm for the constrained maximum flow problem
- Biased predecessor search
- New trie data structures which support very fast search operations
- Dynamic programming with convexity, concavity and sparsity
- Scanline algorithms on a grid
- On graphs preserving rectilinear shortest paths in the presence of obstacles
- Chaining algorithms for multiple genome comparison
- Sorting by bounded block-moves
- Log-logarithmic worst-case range queries are possible in space theta(N)
- EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, kΔ, α)-MATCHING
- Computing the agreement of trees with bounded degrees
- Finding the k Shortest Paths
- Compact recognizers of episode sequences
- An O(m log log D) algorithm for shortest paths
- Output-sensitive generation of the perspective view of isothetic parallelepipeds
- Output-sensitive generation of the perspective view of isothetic parallelepipeds
- A History of Distribution-Sensitive Data Structures
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)
