1 citations · 1 across the 6 of their papers we have counts for
6 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…
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Monika Henzinger, Jason Li, Satish Rao +1
In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time which he termed near-linear time meaning linear (…
Local Flow Partitioning for Faster Edge Connectivity
Monika Henzinger, Satish Rao, Di Wang
We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic time algorithm. This improves both on the best p…