4 papers
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…
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…
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…
Congestion-Approximators from the Bottom Up
Jason Li, Satish Rao, Di Wang
We develop a novel algorithm to construct a congestion-approximator with polylogarithmic quality on a capacitated, undirected graph in nearly-linear time. Our approach is the first…