On the exponent of all pairs shortest path problem
From MaRDI portal
Publication:1356884
DOI10.1006/jcss.1997.1388zbMath0877.68090OpenAlexW2618199688MaRDI QIDQ1356884
Zvi Galil, Olded Margalit, Noga Alon
Publication date: 8 December 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1997.1388
Related Items
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs, A new approach to all-pairs shortest paths on real-weighted graphs, A survey of the all-pairs shortest paths problem and its variants in graphs, All-pairs shortest paths and the essential subgraph, All pairs shortest paths for graphs with small integer length edges, Faster All-Pairs Shortest Paths via Circuit Complexity, Formally verified algorithms for upper-bounding state space diameters, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Unnamed Item, Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound, Algebraic theory on shortest paths for all flows, Approximate shortest paths in weighted graphs, Path Laplacian matrices: introduction and application to the analysis of consensus in networks, Some results on approximate 1-median selection in metric spaces, Shortest distances as enumeration problem, Unnamed Item, Fast matrix multiplication and its algebraic neighbourhood, Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs, Finding real-valued single-source shortest paths in o(n 3) expected time, Combinatorial algorithms for distributed graph coloring, Approximating the minimum cycle mean, All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time, An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs, Algebraic Theory on Shortest Paths for All Flows, Fully dynamic all pairs shortest paths with real edge weights, All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem, Toward Tight Approximation Bounds for Graph Diameter and Eccentricities, From Circuit Complexity to Faster All-Pairs Shortest Paths, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Matrix multiplication via arithmetic progressions
- Scaling algorithms for network problems
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- Gaussian elimination is not optimal
- Faster algorithms for the shortest path problem
- New Bounds on the Complexity of the Shortest Path Problem
