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

DOI10.1007/BF01553908MaRDI QIDQ1823692zbMATH OpenFDO

Authors Michael Luby, Prabhakar Ragde

Publication date 1989

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01553908

zbMATH Keywords

bidirectonal search algorithmprobabilistic analysistwo-terminal shortest-path problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3982535
• Note on ``A new bidirectional algorithm for shortest paths
• An exact bidirectional pulse algorithm for the constrained shortest path
• A forward-backward single-source shortest paths algorithm
• An empirical investigation of some bicriterion shortest path algorithms
• New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
• Shortest path algorithms for nearly acyclic directed graphs
• A new algorithm for the shortest-path problem
• An Appraisal of Some Shortest-Path Algorithms

Cites work

• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time O(n^2 \log ^2 n)
• A note on two problems in connexion with graphs
• Analytic Inequalities
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3327849 (Why is no real title available?)
• scientific article; zbMATH DE number 3415384 (Why is no real title available?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(14)

• MM: a bidirectional search algorithm that is guaranteed to meet in the middle
• Bidirectional edges problem. I: A simple algorithm
• Optimal path discovery problem with homogeneous knowledge
• scientific article; zbMATH DE number 3982535 (Why is no real title available?)
• Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
• scientific article; zbMATH DE number 1334210 (Why is no real title available?)
• scientific article; zbMATH DE number 2080918 (Why is no real title available?)
• Efficient shortest paths in scale-free networks with underlying hyperbolic geometry
• A forward-backward single-source shortest paths algorithm
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• An exact bidirectional pulse algorithm for the constrained shortest path
• Sublinear time shortest path in expander graphs
• Note on ``A new bidirectional algorithm for shortest paths

This page was built for publication: A bidirectional shortest-path algorithm with good average-case behavior

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