3 papers
cs.DS2025
Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
Antoine El-Hayek, Monika Henzinger, Jason Li
We present an exact fully-dynamic minimum cut algorithm that runs in deterministic update time when the minimum cut size is at most for any …
cs.DS2025
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.DS2025
Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Antoine El-Hayek, Monika Henzinger, Jason Li
Dynamically maintaining the minimum cut in a graph under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound…