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
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
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 (25)
- Subquadratic algorithms for algebraic 3SUM
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Faster All-Pairs Shortest Paths via Circuit Complexity
- A survey of the all-pairs shortest paths problem and its variants in graphs
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Many distances in planar graphs
- Algorithms and Computation
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- From Circuit Complexity to Faster All-Pairs Shortest Paths
- Dynamic Set Intersection
- 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
- Title not available (Why is that?)
- Design and Engineering of External Memory Traversal Algorithms for General Graphs
- Title not available (Why is that?)
- 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
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Algebraic methods in the congested clique
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
- Improved subquadratic 3SUM
- Title not available (Why is that?)
- Necklaces, convolutions, and \(X+Y\)
Recommendations
- Algorithms and Data Structures 👍 👎
- An O(n 3 loglogn/log2 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 👍 👎
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)
