An O(n^3( n / n )^5/4) time algorithm for all pairs shortest path

DOI10.1007/S00453-007-9063-0zbMATH Open1147.68092OpenAlexW2114365471MaRDI QIDQ930607FDOQ930607

Yijie Han

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9063-0

zbMATH Keywords

AlgorithmsComplexityGraph algorithmsShortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Algorithms – ESA 2005
• All pairs shortest distances for graphs with small integer length edges
• 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
• Improved algorithm for all pairs shortest paths
• Undirected single-source shortest paths with positive integer weights in linear time
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• Algorithms and Data Structures
• Algorithms and Computation
• Improved parallel integer sorting without concurrent writing

Cited In (10)

• Faster All-Pairs Shortest Paths via Circuit Complexity
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• From Circuit Complexity to Faster All-Pairs Shortest Paths
• Average-case complexity of the min-sum matrix product problem
• 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
• Algebraic methods in the congested clique
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
• 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 n )^{5/4})\) time algorithm for all pairs shortest path

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