Faster negative length shortest paths by bootstrapping hop reducers
Abstract
The textbook algorithm for real-weighted single-source shortest paths takes \(O(mn)\) time on a graph with \(m\) edges and \(n\) vertices. The breakthrough algorithm by Fineman takes \(\tilde{O}(mn^{8/9})\) randomized time. The running time was subsequently improved to \(\tilde{O}(mn^{4/5})\) by Huang, Jin, and Quanrud.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Complex Network Analysis Techniques
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 2419–2429
- Publication date
- 1 January 2026
- Language
- EN