A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths

DOI10.1016/j.ipl.2007.08.015zbMath1184.68663OpenAlexW1572758096MaRDI QIDQ2380054

Yijie Han

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.015

zbMATH Keywords

complexityshortest pathanalysis of algorithmsgraph algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ The Floyd-Warshall algorithm on graphs with negative cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Improved algorithm for all pairs shortest paths
• 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
• Algorithms and Data Structures
• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• Algorithms and Computation

This page was built for publication: A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths