Shortest-path problem is not harder than matrix multiplication
From MaRDI portal
Publication:1149782
DOI10.1016/0020-0190(80)90128-3zbMath0454.68069OpenAlexW2089633648MaRDI QIDQ1149782
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
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
