Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

DOI10.1137/0222071MaRDI QIDQ4277537zbMATH OpenOpenAlexFDO

Authors Daphne Koller, David R. Karger, Steven J. Phillips

Publication date 7 February 1994

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

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

zbMATH Keywords

all-pairs shortest pathslower boundpath comparisonrandom graphsweighted graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• All-pairs shortest paths in \(O(n^2)\) time with high probability
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Algorithms and Data Structures
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• scientific article; zbMATH DE number 986995

Cited in

(30)

• Euclidean TSP between two nested convex obstacles
• An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs
• A new approach to all-pairs shortest paths on real-weighted graphs
• All-pairs shortest paths and the essential subgraph
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs
• Euclidean TSP on two polygons
• Solving all-pairs shortest path by single-source computations: theory and practice
• Approximating the restricted 1-center in graphs
• scientific article; zbMATH DE number 1617277 (Why is no real title available?)
• On the power of tree-depth for fully polynomial FPT algorithms
• Approximating the Restricted 1-Center in Graphs
• Sharing information for the all pairs shortest path problem
• Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
• Running time analysis of ant colony optimization for shortest path problems
• scientific article; zbMATH DE number 1416161 (Why is no real title available?)
• Networks cannot compute their diameter in sublinear time
• Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
• An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
• On the all-pairs shortest path algorithm of Moffat and Takaoka
• Shortest distances as enumeration problem
• On dynamic shortest paths problems
• Near optimal algorithm for the directed single source replacement paths problem
• Simplifying and unifying replacement paths algorithms in weighted directed graphs
• Two algorithms for shortest-paths problems in edge-weighted directed graphs
• A nearly linear time construction of approximate single-source distance sensitivity oracles
• Incremental distance products via faulty shortest paths
• Two fast algorithms for all-pairs shortest paths
• Average-case complexity of the min-sum matrix product problem
• Reconstructing shortest paths

This page was built for publication: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

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