3 papers
cs.DS2025
Faster negative length shortest paths by bootstrapping hop reducers
Yufan Huang, Peter Jin, Kent Quanrud
The textbook algorithm for real-weighted single-source shortest paths takes time on a graph with edges and vertices. The breakthrough algorithm by Fineman [Fin24]…
cs.DS2025
From Hop Reduction to Sparsification for Negative Length Shortest Paths
Kent Quanrud, Navid Tajkhorshid
The textbook algorithm for real-weighted single-source shortest paths takes time on a graph with edges and vertices. A recent breakthrough algorithm by [Fin24] take…
cs.DS2024
Faster single-source shortest paths with negative real weights via proper hop distance
Yufan Huang, Peter Jin, Kent Quanrud
The textbook algorithm for single-source shortest paths with real-valued edge weights runs in time on a graph with edges and vertices. A recent breakthrough algori…