All-pairs shortest paths and the essential subgraph

DOI10.1007/BF01190847zbMath0837.68084MaRDI QIDQ1894298

C. C. McGeoch

Publication date: 9 August 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

digraphall-pairs shortest pathsessential subgraphessential subgraphs

Mathematics Subject Classification ID

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)$