Showing 2024Show all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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 (…