Integer priority queues with decrease key in constant time and the single source shortest paths problem

DOI10.1016/j.jcss.2004.04.003zbMath1084.68030OpenAlexW3031415405WikidataQ56078254 ScholiaQ56078254MaRDI QIDQ5917573

Mikkel Thorup

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.003

zbMATH Keywords

Decrease keyFibonacci heapsInteger priority queuesSingle source shortest paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items

A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ New method in information processing for maintaining an efficient dynamic ordered set ⋮ Mvtree for hierarchical network representation based on geometric algebra subspace ⋮ Succinct encodings for families of interval graphs ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ Splitting algebras and Gysin homomorphisms ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Shortest distances as enumeration problem ⋮ The saga of minimum spanning trees ⋮ Parsimonious formulations for low-diameter clusters ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ A Survey on Priority Queues ⋮ The weighted sitting closer to friends than enemies problem in the line ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Preserving order in a forest in less than logarithmic time and linear space
• Surpassing the information theoretic bound with fusion trees
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Undirected single-source shortest paths with positive integer weights in linear time
• Faster algorithms for the shortest path problem
• Dynamic ordered sets with exponential search trees
• Design and implementation of an efficient priority queue
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Buckets, Heaps, Lists, and Monotone Priority Queues
• On RAM Priority Queues
• Priority queues: Small, monotone and trans-dichotomous
• Optimal bounds for decision problems on the CRCW PRAM
• Deterministic sorting in O(nloglogn) time and linear space
• Fibonacci heaps and their uses in improved network optimization algorithms