1 citations · 1 across the 6 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.DS2025
Shortcutting for Negative-Weight Shortest Path
George Z. Li, Jason Li, Satish Rao +1
Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in time, improving on prior work…
cs.DS2025
Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
Jason Li, Connor Mowry, Satish Rao
We present a faster algorithm for low-diameter decompositions on directed graphs, matching the loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICA…
cs.DS2025
Randomized Bellman-Ford from Fineman and the Boilermakers
Satish Rao
A classical algorithm by Bellman and Ford from the 1950's computes shortest paths in weighted graphs on vertices and edges with possibly negative weights in time. I…