An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
From MaRDI portal
Publication:350723
DOI10.1016/j.jda.2016.09.001zbMath1351.05213MaRDI QIDQ350723
Publication date: 9 December 2016
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2016.09.001
68W40: Analysis of algorithms
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- 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
- All pairs shortest distances for graphs with small integer length edges
- An improved combinatorial algorithm for Boolean matrix multiplication
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- Improved algorithm for all pairs shortest paths
- An O(n 3 loglogn/log2 n) Time 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
- More algorithms for all-pairs shortest paths in weighted graphs
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Regularity Lemmas and Combinatorial Algorithms
- Fibonacci heaps and their uses in improved network optimization algorithms
- Faster all-pairs shortest paths via circuit complexity
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Algorithms and Data Structures
- Algorithms – ESA 2005
- Algorithms and Computation