An algorithm for finding all shortest paths using N^2 81 infinite-precision multiplications

DOI10.1016/0020-0190(76)90085-5MaRDI QIDQ1228358zbMATH OpenOpenAlexWikidataFDO

Authors G. Yuval

Publication date 1976

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

Full work available at URL https://doi.org/10.1016/0020-0190(76)90085-5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cites work

• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)

Cited in

(15)

• Shortest-path problem is not harder than matrix multiplication
• 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?'
• On the exponent of all pairs shortest path problem
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• Approximating the minimum cycle mean
• Bounds for semi-disjoint bilinear forms in a unit-cost computational model
• Approximate shortest paths in weighted graphs
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• Near optimal algorithm for the directed single source replacement paths problem
• (, +) matrix and vector products for inputs decomposable into few monotone subsequences
• Faster monotone min-plus product, range mode, and single source replacement paths
• A priority queue for the all pairs shortest path problem

This page was built for publication: An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1228358)