Shortest-path problem is not harder than matrix multiplication

DOI10.1016/0020-0190(80)90128-3zbMath0454.68069OpenAlexW2089633648MaRDI QIDQ1149782

Francesco Romani

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90128-3

zbMATH Keywords

transitive closure

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

Faster All-Pairs Shortest Paths via Circuit Complexity, Unified all-pairs shortest path algorithms in the chordal hierarchy, Sub-cubic cost algorithms for the all pairs shortest path problem, Complexité de problèmes liés aux graphes sans circuit, The bit-operation complexity of matrix multiplication and of all pair shortest path problem, Unnamed Item, Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, A fast algorithm for finding all shortest paths, A note on 'Is shortest path problem not harder than matrix multiplication?', Author's reply to S. Moran's note on the shortest path problem, Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, A priority queue for the all pairs shortest path problem, The Bounded Path Tree Problem, From Circuit Complexity to Faster All-Pairs Shortest Paths, Bit complexity of matrix products

Cites Work

• Unnamed Item
• Complexity measures for matrix multiplication algorithms
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• Gaussian elimination is not optimal
• Partial and Total Matrix Multiplication