All-pairs shortest paths with real weights in O ( n^3/ n ) time
From MaRDI portal
Publication:2480908
Recommendations
- Algorithms and Data Structures
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
- Algorithms and Computation
Cites work
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1775413 (Why is no real title available?)
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- A more efficient algorithm for the min-plus multiplication
- A new approach to all-pairs shortest paths on real-weighted graphs
- A new upper bound on the complexity of the all pairs shortest path problem
- Algorithms and Computation
- Algorithms – ESA 2004
- All pairs shortest paths for graphs with small integer length edges
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Clique partitions, graph compression and speeding-up algorithms
- Computing and Combinatorics
- Computing dominances in \(E^ n\)
- Gaussian elimination is not optimal
- Improved algorithm for all pairs shortest paths
- Introduction to algorithms
- Matrix multiplication via arithmetic progressions
- New Bounds on the Complexity of the Shortest Path Problem
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On the exponent of all pairs shortest path problem
- Quasiconvex analysis of backtracking algorithms
Cited in
(36)- Dynamic set intersection
- Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Improved time bounds for all pairs non-decreasing paths in general digraphs
- Generalized blocked Floyd-Warshall algorithm
- Algorithms and Data Structures
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Speeding up shortest path algorithms
- Multivariate analysis of orthogonal range searching and graph distances
- scientific article; zbMATH DE number 2086613 (Why is no real title available?)
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Algorithms and Computation
- Faster all-pairs shortest paths via circuit complexity
- An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
- New Bounds on the Complexity of the Shortest Path Problem
- From circuit complexity to faster all-pairs shortest paths
- The Floyd-Warshall algorithm on graphs with negative cycles
- Efficient parameterized algorithms for computing all-pairs shortest paths
- Efficient parameterized algorithms for computing all-pairs shortest paths
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
- Necklaces, convolutions, and \(X+Y\)
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- A new approach to all-pairs shortest paths on real-weighted graphs
- Improved algorithm for all pairs shortest paths
- Subquadratic algorithms for algebraic 3SUM
- Faster algorithms for all-pairs bounded min-cuts
- Multivariate analysis of orthogonal range searching and graph distances
- Design and Engineering of External Memory Traversal Algorithms for General Graphs
- Improved subquadratic 3SUM
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Many distances in planar graphs
- On the Shoshan-Zwick algorithm for the all-pairs shortest path problem
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
This page was built for publication: All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2480908)
