An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths

DOI10.1016/j.jda.2016.09.001zbMath1351.05213OpenAlexW2531762745MaRDI QIDQ350723

Yijie Han, Tadao Takaoka

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

zbMATH Keywords

algorithmsupper boundsgraph algorithmsall pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Parametric Shortest-Path Algorithms via Tropical Geometry

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

This page was built for publication: An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths