An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications

DOI10.1016/0020-0190(76)90085-5zbMath0333.68034OpenAlexW2072985157WikidataQ114215575 ScholiaQ114215575MaRDI QIDQ1228358

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)

Related Items

On the exponent of all pairs shortest path problem, Unified all-pairs shortest path algorithms in the chordal hierarchy, Approximate shortest paths in weighted graphs, 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?', Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, Approximating the minimum cycle mean, Algebraic methods in the congested clique, A priority queue for the all pairs shortest path problem

Cites Work

• Gaussian elimination is not optimal
• Unnamed Item
• Unnamed Item