A note on 'Is shortest path problem not harder than matrix multiplication?'

DOI10.1016/0020-0190(81)90039-9zbMath0474.68078OpenAlexW1997654840MaRDI QIDQ1158968

Shlomo Moran

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90039-9

zbMATH Keywords

reducibilitybitwise complexitytotal arithmetic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Author's reply to S. Moran's note on the shortest path problem ⋮ A priority queue for the all pairs shortest path problem

Cites Work

• Unnamed Item
• Shortest-path problem is not harder than matrix multiplication
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• A lower bound on the number of additions in monotone computations
• Gaussian elimination is not optimal

This page was built for publication: A note on 'Is shortest path problem not harder than matrix multiplication?'