Improved algorithm for all pairs shortest paths
From MaRDI portal
Publication:2390321
DOI10.1016/j.ipl.2004.05.006zbMath1178.68658OpenAlexW2072064573MaRDI QIDQ2390321
Publication date: 21 July 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2004.05.006
Related Items
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, 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, \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs, An improved Dijkstra's shortest path algorithm for sparse network, 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, An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem, 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
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- A new upper bound on the complexity of the all pairs shortest path problem
- All pairs shortest distances for graphs with small integer length edges
- 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
- Fibonacci heaps and their uses in improved network optimization algorithms
- Time and tape complexity of pushdown automaton languages
