Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
From MaRDI portal
Publication:4277537
DOI10.1137/0222071zbMath0799.68148OpenAlexW2133768189MaRDI QIDQ4277537
Daphne Koller, Steven J. Phillips, David R. Karger
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (24)
A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Unnamed Item ⋮ All-pairs shortest paths and the essential subgraph ⋮ Approximating the Restricted 1-Center in Graphs ⋮ A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Two fast algorithms for all-pairs shortest paths ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs ⋮ Sharing information for the all pairs shortest path problem ⋮ 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 ⋮ On the all-pairs shortest path algorithm of Moffat and Takaoka ⋮ Average-case complexity of the min-sum matrix product problem ⋮ Approximating the restricted 1-center in graphs ⋮ Running time analysis of ant colony optimization for shortest path problems ⋮ Shortest distances as enumeration problem ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ On dynamic shortest paths problems ⋮ Euclidean TSP on two polygons ⋮ Euclidean TSP between two nested convex obstacles ⋮ Incremental distance products via faulty shortest paths ⋮ Unnamed Item ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
This page was built for publication: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
