More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

DOI10.1137/08071990XzbMath1207.68436OpenAlexW3022326557WikidataQ56170983 ScholiaQ56170983MaRDI QIDQ3053160

Timothy M. Chan

Publication date: 4 November 2010

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

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

zbMATH Keywords

shortest pathsgraph algorithmscomputational geometrymatrix multiplicationAPSPsmall-integer-weighted graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items (25)

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ Dynamic Set Intersection ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Extreme Witnesses and Their Applications ⋮ Online routing and searching on graphs with blocked edges ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Proximity graphs inside large weighted graphs ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Average-case complexity of the min-sum matrix product problem ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Unnamed Item ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Necklaces, convolutions, and \(X+Y\) ⋮ Approximating the minimum cycle mean ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ Algebraic methods in the congested clique ⋮ Extreme witnesses and their applications ⋮ More on change-making and related problems ⋮ Small-\(m\) method for detecting all longest paths ⋮ Vertex labeling and routing for Farey-type symmetrically-structured graphs ⋮ 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

This page was built for publication: More Algorithms for All-Pairs Shortest Paths in Weighted Graphs