New Bounds on the Complexity of the Shortest Path Problem

DOI10.1137/0205006zbMATH Open0326.68027OpenAlexW2028341270MaRDI QIDQ4091447FDOQ4091447

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

Recommendations

A new upper bound on the complexity of the all pairs shortest path problem
All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
scientific article; zbMATH DE number 219247
A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
scientific article; zbMATH DE number 1979485

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

Cited In (60)

Directed shortest paths via approximate cost balancing
Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
Parametric shortest-path algorithms via tropical geometry
Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
Monge and feasibility sequences in general flow problems
On the optimality of Bellman-Ford-Moore shortest path algorithm
Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs
Simple rectangle-based functional programs for computing reflexive-transitive closures
The bit-operation complexity of matrix multiplication and of all pair shortest path problem
Some graft transformations and its applications on the distance spectral radius of a graph
Efficient parameterized algorithms for computing all-pairs shortest paths
A survey of the all-pairs shortest paths problem and its variants in graphs
Efficient transitive closure of sparse matrices over closed semirings
A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
Improved algorithm for all pairs shortest paths
Efficient parallel algorithms for shortest paths in planar digraphs
On the exponent of all pairs shortest path problem
Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Faster all-pairs shortest paths via circuit complexity
New bounds for multi-label interval routing
Fully dynamic all pairs shortest paths with real edge weights
All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
Title not available (Why is that?)
Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
Computation of shortest path in cellular automata
All-pairs shortest paths and the essential subgraph
On the minimal distance spectral radius in the class of bicyclic graphs
A lower bound for the shortest path problem
Searching among intervals and compact routing tables
The shortest-path problem for graphs with random arc-lengths
Distance spectra of graphs: a survey
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
A new approach to all-pairs shortest paths on real-weighted graphs
Formally verified algorithms for upper-bounding state space diameters
On the maximal distance spectral radius in a class of bicyclic graphs
An all-pairs shortest path algorithm for bipartite graphs
An Improved Distribution Algorithm for Shortest Paths Problem
Average-case complexity of the min-sum matrix product problem
Connectivity and minimal distance spectral radius of graphs
An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
Complexité de problèmes liés aux graphes sans circuit
Searching among intervals and compact routing tables
Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures
The Floyd-Warshall algorithm on graphs with negative cycles
Approximating the minimum cycle mean
From circuit complexity to faster all-pairs shortest paths
An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
A priority queue for the all pairs shortest path problem
An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
Distance spectral radius of trees with fixed number of pendent vertices
On the all-pairs shortest path algorithm of Moffat and Takaoka
A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem
A new upper bound on the complexity of the all pairs shortest path problem
Title not available (Why is that?)
Efficient parallel algorithms for shortest paths in planar graphs
Necklaces, convolutions, and \(X+Y\)
The single train shortest route problem in a railyard
Title not available (Why is that?)
Efficient parallel algorithms for computing all pair shortest paths in directed graphs

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

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