More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
From MaRDI portal
Publication:3053160
DOI10.1137/08071990XzbMath1207.68436WikidataQ56170983 ScholiaQ56170983MaRDI QIDQ3053160
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
shortest paths; graph algorithms; computational geometry; matrix multiplication; APSP; small-integer-weighted graphs
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68W05: Nonnumerical algorithms
Related Items
Faster All-Pairs Shortest Paths via Circuit Complexity, Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, From Circuit Complexity to Faster All-Pairs Shortest Paths, Proximity graphs inside large weighted graphs, Unnamed Item, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Efficient parameterized algorithms for computing all-pairs shortest paths, Some results on approximate 1-median selection in metric spaces, Necklaces, convolutions, and \(X+Y\), Sparse RNA folding: time and space efficient algorithms, Average-case complexity of the min-sum matrix product problem, Formally verified algorithms for upper-bounding state space diameters, Extreme witnesses and their applications, Algebraic methods in the congested clique, More on change-making and related problems, Online routing and searching on graphs with blocked edges, Approximating the minimum cycle mean, Small-\(m\) method for detecting all longest paths, Vertex labeling and routing for Farey-type symmetrically-structured 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, A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs, Dynamic Set Intersection, Extreme Witnesses and Their Applications
