An O(n ^3 n/ ^2 n) time algorithm for all pairs shortest paths
From MaRDI portal
Publication:2904549
DOI10.1007/978-3-642-31155-0_12zbMATH Open1357.05145OpenAlexW1608550999MaRDI QIDQ2904549FDOQ2904549
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
Recommendations
- An \(O(n^3 \log \log n / \log^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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Paths and cycles (05C38)
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
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- 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
- 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
- Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- Base-object location problems for base-monotone regions
- Title not available (Why is that?)
- Average-case complexity of the min-sum matrix product problem
- Algorithms and Data Structures
- An \(O(n^3 \log \log n / \log^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)
