All-pairs shortest paths and the essential subgraph
From MaRDI portal
Publication:1894298
DOI10.1007/BF01190847zbMath0837.68084MaRDI QIDQ1894298
Publication date: 9 August 1995
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Unnamed Item ⋮ Two fast algorithms for all-pairs shortest paths ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs ⋮ Average-case complexity of the min-sum matrix product problem
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On the value of a random minimum spanning tree problem
- The shortest-path problem for graphs with random arc-lengths
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- On the exponent of all pairs shortest path problem
- Faster algorithms for the shortest path problem
- A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
- On Shortest Paths in Graphs with Random Weights
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- Generating Sorted Lists of Random Numbers
- Random Graphs and Graph Optimization Problems
- On finding and updating shortest paths distributively
- New Bounds on the Complexity of the Shortest Path Problem
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
