New Bounds on the Complexity of the Shortest Path Problem
From MaRDI portal
Publication:4091447
DOI10.1137/0205006zbMath0326.68027OpenAlexW2028341270MaRDI QIDQ4091447
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Algorithms in computer science (68W99)
Related Items
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
