On RAM Priority Queues

DOI10.1137/S0097539795288246MaRDI QIDQ4507340zbMATH OpenWikidataFDO

Authors Mikkel Thorup

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

shortest pathsgreedy algorithmssortingpriority queuesRAM model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 871900
• Fast priority queues for cached memory
• Priority queues
• Priority Queues Resilient to Memory Faults
• Randomized priority queues for fast parallel access
• scientific article; zbMATH DE number 1760164
• Worst-case efficient external-memory priority queues
• An experimental study of priority queues in external memory
• Priority queues on parallel machines
• Priority queues on parallel machines

Cited in

(32)

• scientific article; zbMATH DE number 2111732 (Why is no real title available?)
• Weighted fusion graphs: Merging properties and watersheds
• New presentations of a link and virtual link
• An experimental study of priority queues in external memory
• Worst-case efficient external-memory priority queues
• Dynamic layers of maxima with applications to dominating queries
• Two-Level Heaps: A New Priority Queue Structure with Applications to the Single Source Shortest Path Problem
• Cascade heap: towards time-optimal extractions
• Cascade heap: towards time-optimal extractions
• New method in information processing for maintaining an efficient dynamic ordered set
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Rank-Sensitive Priority Queues
• Priority-Consistent Graphs
• scientific article; zbMATH DE number 6469188 (Why is no real title available?)
• A faster polynomial algorithm for the constrained maximum flow problem
• A double scaling algorithm for the constrained maximum flow problem
• A novel pseudo‐polynomial approach for shortest path problems
• The power of choice in priority scheduling
• Variable-priority queue and doughnut routing
• Two-level heaps: a new priority queue structure with applications to the single source shortest path problem
• scientific article; zbMATH DE number 1476490 (Why is no real title available?)
• Hash functions for priority queues
• scientific article; zbMATH DE number 6469130 (Why is no real title available?)
• Dynamic interpolation search revisited
• Priority queues: small, monotone and trans-dichotomous
• Improved bounds for finger search on a RAM
• Ordered priority queues
• Twol-amalgamated priority queues
• Probabilistic data structures for priority queues
• A simple implementation technique for priority search queues
• A survey on priority queues
• A novel linear algorithm for shortest paths in networks

This page was built for publication: On RAM Priority Queues

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