A new approach to all-pairs shortest paths on real-weighted graphs

DOI10.1016/S0304-3975(03)00402-XzbMath1071.68084WikidataQ56078250 ScholiaQ56078250MaRDI QIDQ1884872

Seth Pettie

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

All-pairs shortest pathsComparison-addition modelReal weights

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (41)

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 ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Approximating the Restricted 1-Center in Graphs ⋮ A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs ⋮ Solving shortest paths efficiently on nearly acyclic directed graphs ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ Solving all-pairs shortest path by single-source computations: theory and practice ⋮ Two fast algorithms for all-pairs shortest paths ⋮ 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 ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs ⋮ Approximating the restricted 1-center in graphs ⋮ Factorization and pseudofactorization of weighted graphs ⋮ 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 ⋮ Shortest distances as enumeration problem ⋮ On bounded leg shortest paths problems ⋮ On dynamic shortest paths problems ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems ⋮ A spectral approach to the shortest path problem ⋮ Unnamed Item ⋮ 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 ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ Efficient single-pair all-shortest-path query processing for massive dynamic networks ⋮ Design and Engineering of External Memory Traversal Algorithms for General Graphs ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A class of algorithms which require nonlinear time to maintain disjoint sets
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• A new upper bound on the complexity of the all pairs shortest path problem
• On the exponent of all pairs shortest path problem
• All pairs shortest distances for graphs with small integer length edges
• Undirected single-source shortest paths with positive integer weights in linear time
• An optimal minimum spanning tree algorithm
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Faster algorithms for the shortest path problem
• Deterministic sorting in O ( n log log n ) time and linear space
• Information Bounds Are Weak in the Shortest Distance Problem
• On Finding and Updating Spanning Trees and Shortest Paths
• New Bounds on the Complexity of the Shortest Path Problem
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Design and implementation of an efficient priority queue
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Faster Scaling Algorithms for Network Problems
• Scaling Algorithms for the Shortest Paths Problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Integer priority queues with decrease key in constant time and the single source shortest paths problem

This page was built for publication: A new approach to all-pairs shortest paths on real-weighted graphs