215 citations · 318 across the 83 of their papers we have counts for
9 papers · 1 filter
Minimum Cuts in Directed Graphs via Partial Sparsification
Ruoxu Cen, Jason Li, Danupon Nanongkai +3
We give an algorithm to find a minimum cut in an edge-weighted directed graph with vertices and edges in time. This improves on the 30 y…
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
Amos Beimel, Haim Kaplan, Yishay Mansour +3
A dynamic algorithm against an adaptive adversary is required to be correct when the adversary chooses the next update after seeing the previous outputs of the algorithm. We obtain…
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li +3
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all pairs of vertices in an undirected graph can be solved using on…
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as -length flows…
Deterministic Weighted Expander Decomposition in Almost-linear Time
Jason Li, Thatchaphol Saranurak
In this note, we study the expander decomposition problem in a more general setting where the input graph has positively weighted edges and nonnegative demands on its vertices. We…
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
We give an -time algorithm for finding - min-cuts for all pairs of vertices and in a simple, undirected graph on vertices. We do so by constructing a…
Minimum Cuts in Directed Graphs via Max-Flows
Ruoxu Cen, Jason Li, Danupon Nanongkai +2
We give an algorithm to find a mincut in an -vertex, -edge weighted directed graph using calls to any maxflow subroutine. Using state of the art maxflow…
Vertex Connectivity in Poly-logarithmic Max-flows
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +2
The vertex connectivity of an -edge -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In thi…
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source to every vertex in an -edge graph undergoing edge deletion…