A more efficient algorithm for the min-plus multiplication
From MaRDI portal
Publication:4009726
DOI10.1080/00207169008803814zbMath0825.68412OpenAlexW2021227709MaRDI QIDQ4009726
Publication date: 27 September 1992
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207169008803814
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (16)
A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Improved algorithm for all pairs shortest paths ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ An all-pairs shortest path algorithm for bipartite graphs ⋮ A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ A new upper bound on the complexity of the all pairs shortest path problem ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Bit complexity of matrix products
Cites Work
This page was built for publication: A more efficient algorithm for the min-plus multiplication
