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

DOI10.1007/978-3-642-31155-0_12MaRDI QIDQ2904549zbMATH OpenOpenAlexFDO

Authors Yijie Han, Tadao Takaoka

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

zbMATH Keywords

algorithmsgraph algorithmsupper boundsall-pairs shortest paths

Mathematics Subject Classification ID

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

Recommendations

• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• Improved algorithm for all pairs shortest paths
• A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time

Cited in

(22)

• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
• Improved algorithm for all pairs shortest paths
• Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
• Faster all-pairs shortest paths via circuit complexity
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• On the Shoshan-Zwick algorithm for the all-pairs shortest path problem
• Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• Base-object location problems for base-monotone regions
• scientific article; zbMATH DE number 3908469 (Why is no real title available?)
• Average-case complexity of the min-sum matrix product problem
• Algorithms and Data Structures
• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• From circuit complexity to faster all-pairs shortest paths
• 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
• A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904549)