Two-level heaps: a new priority queue structure with applications to the single source shortest path problem

DOI10.1007/s00607-010-0112-1zbMath1211.68135OpenAlexW2030803509MaRDI QIDQ607658

Kamesh Madduri, K. Subramani and Vahan Mkrtchyan

Publication date: 23 November 2010

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-010-0112-1

zbMATH Keywords

Dijkstra's algorithmpriority queuesedge relaxationsingle source shortest pathtwo-level heaps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Data structures (68P05) Discrete mathematics in relation to computer science (68R99)

Uses Software

• Netsoft
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the computational complexity of dynamic graph problems
• Shortest paths algorithms: Theory and experimental evaluation
• Faster algorithms for the shortest path problem
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Priority queues: Small, monotone and trans-dichotomous
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Deciding Separation Logic Formulae by SAT and Incremental Negative Cycle Elimination
• Irredundant intervals
• Fast priority queues for cached memory

This page was built for publication: Two-level heaps: a new priority queue structure with applications to the single source shortest path problem