An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
From MaRDI portal
Publication:2904549
DOI10.1007/978-3-642-31155-0_12zbMath1357.05145OpenAlexW1608550999MaRDI QIDQ2904549
Publication date: 14 August 2012
Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31155-0_12
Analysis of algorithms (68W40) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ 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 ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ Average-case complexity of the min-sum matrix product problem ⋮ A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time ⋮ Algebraic methods in the congested clique ⋮ Base-object location problems for base-monotone regions ⋮ 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 ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
This page was built for publication: An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
