A new upper bound on the complexity of the all pairs shortest path problem
From MaRDI portal
Publication:1199881
DOI10.1016/0020-0190(92)90200-FzbMath0763.68044MaRDI QIDQ1199881
Publication date: 17 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (28)
A new approach to all-pairs shortest paths on real-weighted graphs ⋮ 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 ⋮ External matrix multiplication and all-pairs shortest path ⋮ Improved algorithm for all pairs shortest paths ⋮ THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS ⋮ Minmax regret location--allocation problem on a network under uncertainty ⋮ 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 ⋮ On the all-pairs shortest path algorithm of Moffat and Takaoka ⋮ Sub-cubic cost algorithms for the all pairs shortest path problem ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ 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 ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ Efficient parallel algorithms for computing all pair shortest paths in directed graphs ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ The Floyd-Warshall algorithm on graphs with negative cycles ⋮ Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication ⋮ A selected tour of the theory of identification matrices ⋮ An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ 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
- Bit complexity of matrix products
- Binary Trees and Parallel Scheduling Algorithms
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- Parallel Matrix and Graph Algorithms
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
This page was built for publication: A new upper bound on the complexity of the all pairs shortest path problem
