On the optimality of Bellman-Ford-Moore shortest path algorithm

DOI10.1016/J.TCS.2016.03.014MaRDI QIDQ266282zbMATH OpenOpenAlexFDO

Authors Georg Schnitger, Stasys Jukna

Publication date 13 April 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.03.014

zbMATH Keywords

dynamic programmingshortest pathslower boundsmatrix multiplicationtropical semiring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39)

Recommendations

• A new algorithm for the shortest-path problem
• A lower bound for the shortest path problem
• Scaling Algorithms for the Shortest Paths Problem
• New Bounds on the Complexity of the Shortest Path Problem
• Shortest paths in almost acyclic graphs

Cites work

• scientific article; zbMATH DE number 3207626 (Why is no real title available?)
• scientific article; zbMATH DE number 3261634 (Why is no real title available?)
• A Theorem on Boolean Matrices
• Complexity of monotone networks for Boolean matrix product
• Formulas vs. circuits for small distance connectivity
• Lower bounds for tropical circuits and dynamic programs
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone switching circuits and Boolean matrix product
• On a routing problem
• On maximal paths and circuits of graphs
• Reliable circuits using less reliable relays
• Some Theorems on Abstract Graphs
• The Power of Negative Thinking in Multiplying Boolean Matrices

Cited in

(6)

• scientific article; zbMATH DE number 3974765 (Why is no real title available?)
• Improvement and experimental evaluation on classical Bellman-Ford algorithm
• Lower bounds for non-adaptive shortest path relaxation
• scientific article; zbMATH DE number 7204408 (Why is no real title available?)
• Hybrid Bellman-Ford-Dijkstra algorithm
• Randomized Speedup of the Bellman–Ford Algorithm

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: On the optimality of Bellman-Ford-Moore shortest path algorithm

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