Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
From MaRDI portal
Recommendations
- All-pairs shortest paths in \(O(n^2)\) time with high probability
- A simplified 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 simpler algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
- On the all-pairs shortest path algorithm of Moffat and Takaoka
Cites work
- A guided tour of Chernoff bounds
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time O(n^2 \log ^2 n)
- A new approach to all-pairs shortest paths on real-weighted graphs
- A new approach to dynamic all pairs shortest paths
- A note on two problems in connexion with graphs
- A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
- A Theorem on Boolean Matrices
- All-pairs shortest paths in \(O(n^2)\) time with high probability
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Experimental analysis of dynamic all pairs shortest path algorithms
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- scientific article; zbMATH DE number 986995 (Why is no real title available?)
- scientific article; zbMATH DE number 3700238 (Why is no real title available?)
- scientific article; zbMATH DE number 1301967 (Why is no real title available?)
- scientific article; zbMATH DE number 1926665 (Why is no real title available?)
- scientific article; zbMATH DE number 1416161 (Why is no real title available?)
- Network flows. Theory, algorithms, and applications.
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- Shortest paths algorithms: Theory and experimental evaluation
- Solving all-pairs shortest path by single-source computations: theory and practice
- The longest minimum-weight path in a complete graph
This page was built for publication: Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5862374)
