Shortest-path problem is not harder than matrix multiplication
From MaRDI portal
Publication:1149782
DOI10.1016/0020-0190(80)90128-3zbMath0454.68069MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
Unnamed Item, The Bounded Path Tree Problem, A priority queue for the all pairs shortest path problem, Bit complexity of matrix products, The bit-operation complexity of matrix multiplication and of all pair shortest path problem, 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, Unified all-pairs shortest path algorithms in the chordal hierarchy, Complexité de problèmes liés aux graphes sans circuit
Cites Work
