A Shortest Path Algorithm for Real-Weighted Undirected Graphs
From MaRDI portal
Publication:5317203
DOI10.1137/S0097539702419650zbMath1078.05080OpenAlexW2065105907MaRDI QIDQ5317203
Vijaya Ramachandran, Seth Pettie
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702419650
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Efficient algorithms for the round-trip 1-center and 1-median problems ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Proximity graphs inside large weighted graphs ⋮ On the second point-to-point undirected shortest simple path problem ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Continuous mean distance of a weighted graph ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Shortest distances as enumeration problem ⋮ On dynamic shortest paths problems ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ Hybrid Bellman-Ford-Dijkstra algorithm ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item
