scientific article; zbMATH DE number 3982535

MaRDI QIDQ3746901zbMATH OpenFDO

Authors Michael Luby, Prabhakar Ragde

Publication date 1985

zbMATH Keywords

average-case analysisbidirectional search algorithmcomplete directed graphDijkstra's algorithmpriority queue implementationprobabilistic modeltwo-terminal shortest-path problem

Mathematics Subject Classification ID

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

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

Cited in

(6)

• 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
• scientific article; zbMATH DE number 1334210 (Why is no real title available?)
• An exact bidirectional pulse algorithm for the constrained shortest path
• Note on ``A new bidirectional algorithm for shortest paths

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)