An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
From MaRDI portal
Publication:1044727
DOI10.1016/j.ipl.2005.08.008zbMath1191.68473OpenAlexW1999222448MaRDI QIDQ1044727
Publication date: 18 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.08.008
Related Items (12)
A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ 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 ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ 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
- A new upper bound on the complexity of the all pairs shortest path problem
- On the exponent of all pairs shortest path problem
- Subcubic cost algorithms for the all pairs shortest path problem
- Improved algorithm for all pairs shortest paths
- On the computational power of pushdown automata
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Computing and Combinatorics
- Algorithms and Computation
This page was built for publication: An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
