A bidirectional shortest-path algorithm with good average-case behavior

DOI10.1007/BF01553908zbMath0681.68068MaRDI QIDQ1823692

Prabhakar Ragde, Michael Luby

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

probabilistic analysisbidirectonal search algorithmtwo-terminal shortest-path problem

Mathematics Subject Classification ID

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

Related Items

MM: a bidirectional search algorithm that is guaranteed to meet in the middle, Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Optimal path discovery problem with homogeneous knowledge, A Forward-Backward Single-Source Shortest Paths Algorithm

Cites Work

• A note on two problems in connexion with graphs
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Analytic Inequalities
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item