All-pairs shortest paths with real weights in O ( n^3/ n ) time
From MaRDI portal
Publication:2480908
DOI10.1007/S00453-007-9062-1zbMATH Open1151.68043OpenAlexW2623873233MaRDI QIDQ2480908FDOQ2480908
Authors: Timothy M. Chan 
Publication date: 3 April 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9062-1
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Introduction to algorithms
- Gaussian elimination is not optimal
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Computing dominances in \(E^ n\)
- A new approach to all-pairs shortest paths on real-weighted graphs
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Title not available (Why is that?)
- Clique partitions, graph compression and speeding-up algorithms
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- A new upper bound on the complexity of the all pairs shortest path problem
- Improved algorithm for all pairs shortest paths
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Algorithms and Computation
- On the exponent of all pairs shortest path problem
- Computing and Combinatorics
- All pairs shortest paths for graphs with small integer length edges
- Title not available (Why is that?)
- Algorithms – ESA 2004
- Quasiconvex analysis of backtracking algorithms
Cited In (36)
- Multivariate analysis of orthogonal range searching and graph distances
- Subquadratic algorithms for algebraic 3SUM
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Generalized blocked Floyd-Warshall algorithm
- Faster algorithms for all-pairs bounded min-cuts
- Dynamic set intersection
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- 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
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- Improved algorithm for all pairs shortest paths
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Many distances in planar graphs
- Algorithms and Computation
- Faster all-pairs shortest paths via circuit complexity
- On the Shoshan-Zwick algorithm for the all-pairs shortest path problem
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- New Bounds on the Complexity of the Shortest Path Problem
- A new approach to all-pairs shortest paths on real-weighted graphs
- A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
- Algorithms and Data Structures
- Title not available (Why is that?)
- Design and Engineering of External Memory Traversal Algorithms for General Graphs
- An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
- Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
- The Floyd-Warshall algorithm on graphs with negative cycles
- Multivariate analysis of orthogonal range searching and graph distances
- From circuit complexity to faster all-pairs shortest paths
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Improved subquadratic 3SUM
- Improved time bounds for all pairs non-decreasing paths in general digraphs
- Necklaces, convolutions, and \(X+Y\)
- Speeding up shortest path algorithms
- 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)
