An O(n^3 n/ n) time algorithm for the all-pairs shortest path problem
From MaRDI portal
Publication:1044727
Recommendations
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
- An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- A simpler algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
- scientific article; zbMATH DE number 3908469
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
Cites work
- A more efficient algorithm for the min-plus multiplication
- A new upper bound on the complexity of the all pairs shortest path problem
- Algorithms and Computation
- Computing and Combinatorics
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- Improved algorithm for all pairs shortest paths
- New Bounds on the Complexity of the Shortest Path Problem
- On the computational power of pushdown automata
- On the exponent of all pairs shortest path problem
- Subcubic cost algorithms for the all pairs shortest path problem
Cited in
(15)- A new upper bound on the complexity of the all pairs shortest path problem
- A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- Faster all-pairs shortest paths via circuit complexity
- Computing and Combinatorics
- From circuit complexity to faster all-pairs shortest paths
- A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- The Floyd-Warshall algorithm on graphs with negative cycles
This page was built for publication: An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1044727)
