All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
From MaRDI portal
Publication:2480908
DOI10.1007/s00453-007-9062-1zbMath1151.68043MaRDI QIDQ2480908
Publication date: 3 April 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9062-1
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Faster All-Pairs Shortest Paths via Circuit Complexity, Unnamed Item, Unnamed Item, From Circuit Complexity to Faster All-Pairs Shortest Paths, Many distances in planar graphs, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Improved subquadratic 3SUM, Necklaces, convolutions, and \(X+Y\), Multivariate analysis of orthogonal range searching and graph distances, The Floyd-Warshall algorithm on graphs with negative cycles, Algebraic methods in the congested clique, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, Subquadratic algorithms for algebraic 3SUM, 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, Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound, Dynamic Set Intersection, Design and Engineering of External Memory Traversal Algorithms for General Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- 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
- Computing dominances in \(E^ n\)
- A new upper bound on the complexity of the all pairs shortest path problem
- All pairs shortest paths for graphs with small integer length edges
- On the exponent of all pairs shortest path problem
- A new approach to all-pairs shortest paths on real-weighted graphs
- Clique partitions, graph compression and speeding-up algorithms
- Improved algorithm for all pairs shortest paths
- Gaussian elimination is not optimal
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- A more efficient algorithm for the min-plus multiplication
- New Bounds on the Complexity of the Shortest Path Problem
- Computing and Combinatorics
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Algorithms – ESA 2004
- Quasiconvex Analysis of Backtracking Algorithms
- Algorithms and Computation
