A faster all-pairs shortest path algorithm for real-weighted sparse graphs

DOI10.1007/3-540-45465-9_9MaRDI QIDQ4737147zbMATH OpenFDO

Authors Seth Pettie

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800085.htm

Mathematics Subject Classification ID

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

Recommendations

• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Algorithms and Data Structures
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• A new approach to all-pairs shortest paths on real-weighted graphs
• Speeding up shortest path algorithms

Cited in

(17)

• A new approach to all-pairs shortest paths on real-weighted graphs
• A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
• Improved algorithm for all pairs shortest paths
• Solving all-pairs shortest path by single-source computations: theory and practice
• Discrete sensor placement problems in distribution networks
• Computing all-pairs shortest paths by leveraging low treewidth
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
• Path Laplacian matrices: introduction and application to the analysis of consensus in networks
• scientific article; zbMATH DE number 2119672 (Why is no real title available?)
• Speeding up shortest path algorithms
• Approximation algorithms for min-distance problems
• All-pairs shortest paths algorithm for high-dimensional sparse graphs
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Approximation algorithms for min-distance problems in DAGs
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path

This page was built for publication: A faster all-pairs shortest path algorithm for real-weighted sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4737147)