38 citations · 53 across the 13 of their papers we have counts for
3 papers · 2 filters
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 $\…