An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths

DOI10.1007/11841036_38zbMath1131.68464OpenAlexW2154848433MaRDI QIDQ5449546

Yijie Han

Publication date: 11 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11841036_38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

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 ⋮ \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem ⋮ The Floyd-Warshall algorithm on graphs with negative cycles

This page was built for publication: An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths