New Bounds on the Complexity of the Shortest Path Problem

DOI10.1137/0205006zbMath0326.68027OpenAlexW2028341270MaRDI QIDQ4091447

Michael L. Fredman

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0205006

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Algorithms in computer science (68W99)

Related Items (54)

The shortest-path problem for graphs with random arc-lengths ⋮ Efficient transitive closure of sparse matrices over closed semirings ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ New bounds for multi-label interval routing ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ Efficient parallel algorithms for shortest paths in planar graphs ⋮ All-pairs shortest paths and the essential subgraph ⋮ A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ Searching among intervals and compact routing tables ⋮ On the exponent of all pairs shortest path problem ⋮ Simple Rectangle-Based Functional Programs for Computing Reflexive-Transitive Closures ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Improved algorithm for all pairs shortest paths ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Searching among intervals and compact routing tables ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Computation of shortest path in cellular automata ⋮ Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ On the all-pairs shortest path algorithm of Moffat and Takaoka ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ Average-case complexity of the min-sum matrix product problem ⋮ Complexité de problèmes liés aux graphes sans circuit ⋮ Some graft transformations and its applications on the distance spectral radius of a graph ⋮ The bit-operation complexity of matrix multiplication and of all pair shortest path problem ⋮ Unnamed Item ⋮ Distance spectral radius of trees with fixed number of pendent vertices ⋮ An all-pairs shortest path algorithm for bipartite graphs ⋮ A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ The single train shortest route problem in a railyard ⋮ ON THE MAXIMAL DISTANCE SPECTRAL RADIUS IN A CLASS OF BICYCLIC GRAPHS ⋮ Efficient parallel algorithms for computing all pair shortest paths in directed graphs ⋮ Efficient parallel algorithms for shortest paths in planar digraphs ⋮ Necklaces, convolutions, and \(X+Y\) ⋮ Monge and feasibility sequences in general flow problems ⋮ ON THE MINIMAL DISTANCE SPECTRAL RADIUS IN THE CLASS OF BICYCLIC GRAPHS ⋮ A new upper bound on the complexity of the all pairs shortest path problem ⋮ Distance spectra of graphs: a survey ⋮ Approximating the minimum cycle mean ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Algebraic methods in the congested clique ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ The Floyd-Warshall algorithm on graphs with negative cycles ⋮ Connectivity and minimal distance spectral radius of graphs ⋮ An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem ⋮ A priority queue for the all pairs shortest path problem ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures ⋮ Parametric Shortest-Path Algorithms via Tropical Geometry

This page was built for publication: New Bounds on the Complexity of the Shortest Path Problem