More algorithms for all-pairs shortest paths in weighted graphs
From MaRDI portal
Publication:3549660
DOI10.1145/1250790.1250877zbMath1231.05245OpenAlexW2152290683MaRDI QIDQ3549660
Publication date: 5 January 2009
Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1250790.1250877
Analysis of algorithms (68W40) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22) Flows in graphs (05C21)
Related Items (32)
Efficient algorithms for the round-trip 1-center and 1-median problems ⋮ Speeding up HMM decoding and training by exploiting sequence repetitions ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ Memory-Efficient Sparse Matrix-Matrix Multiplication by Row Merging on Many-Core Architectures ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ 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 ⋮ Approximate shortest paths in weighted graphs ⋮ A shortest cycle for each vertex of a graph ⋮ A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Accelerating Viterbi algorithm on graphics processing units ⋮ A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ Edit Distance with Duplications and Contractions Revisited ⋮ Faster algorithms for guided tree edit distance ⋮ Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ The Floyd-Warshall algorithm on graphs with negative cycles ⋮ Approximating Shortest Paths in Graphs ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ Sparse RNA Folding: Time and Space Efficient Algorithms ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Computing the dilation of edge-augmented graphs in metric spaces ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distance multiplication of unit-Monge matrices
This page was built for publication: More algorithms for all-pairs shortest paths in weighted graphs
