215 citations · 689 across the 60 of their papers we have counts for
6 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…
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…
A Note on Isolating Cut Lemma for Submodular Function Minimization
Sagnik Mukhopadhyay, Danupon Nanongkai
It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the…
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For for any constant , our algorit…
Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay +1
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $\…