An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
From MaRDI portal
Publication:930607
DOI10.1007/s00453-007-9063-0zbMath1147.68092OpenAlexW2114365471MaRDI QIDQ930607
Publication date: 1 July 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9063-0
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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, Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound, Average-case complexity of the min-sum matrix product problem, Algebraic methods in the congested clique, The Floyd-Warshall algorithm on graphs with negative cycles, From Circuit Complexity to Faster All-Pairs Shortest Paths, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- 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 parallel integer sorting without concurrent writing
- All pairs shortest distances for graphs with small integer length edges
- Improved algorithm for all pairs shortest paths
- Undirected single-source shortest paths with positive integer weights in linear time
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Algorithms and Data Structures
- Algorithms – ESA 2005
- Algorithms and Computation
