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

DOI10.1016/j.tcs.2016.03.014zbMath1339.90327OpenAlexW2294351956MaRDI QIDQ266282

Georg Schnitger, Stasys P. 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 programminglower boundsshortest pathsmatrix multiplicationtropical semiring

Mathematics Subject Classification ID

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

Related Items (2)

Lower bounds for non-adaptive shortest path relaxation ⋮ Unnamed Item

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for tropical circuits and dynamic programs
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• On a routing problem
• On maximal paths and circuits of graphs
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Formulas vs. circuits for small distance connectivity
• A Theorem on Boolean Matrices
• Reliable circuits using less reliable relays
• Some Theorems on Abstract Graphs

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