Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
Graph algorithm
A Note on Isolating Cut Lemma for Submodular Function Minimization
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 non-trivial minimizer of a symmetric submodular function and solving the hypergraph minimum cut problem.
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
arXiv
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$, our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability.
Andrés López-Martínez
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Video
arXiv
Distributed Weighted Min-Cut in Nearly-Optimal Time
Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.
Michal Dory
,
Yuval Efron
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Video
arXiv
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$.
Sagnik Mukhopadhyay
,
Danupon Nanongkai
PDF
Slides
Video
arXiv
Cite
×