scientific article; zbMATH DE number 3982535

zbMATH Open0607.68051MaRDI QIDQ3746901FDOQ3746901

Authors: Michael Luby, Prabhakar Ragde 

Publication date: 1985

Title of this publication is not available (Why is that?)

Recommendations

• A bidirectional shortest-path algorithm with good average-case behavior
• A theorem on the expected complexity of dijkstra's shortest path algorithm
• Faster algorithms for the shortest path problem
• A Practical Shortest Path Algorithm with Linear Expected Time
• Simpler computation of single-source shortest paths in linear average time

zbMATH Keywords

average-case analysisprobabilistic modelDijkstra's algorithmcomplete directed graphtwo-terminal shortest-path problembidirectional search algorithmpriority queue implementation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Cited In (5)

• An exact bidirectional pulse algorithm for the constrained shortest path
• Note on ``A new bidirectional algorithm for shortest paths
• A new bidirectional search algorithm with shortened postprocessing
• A bidirectional shortest-path algorithm with good average-case behavior
• A theorem on the expected complexity of dijkstra's shortest path algorithm

This page was built for publication:

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