Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
Min-cut
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition
We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min{\lambda n^2, n^r/\lambda})$, where $p$ is the size, $n$ is the number of vertices, $r$ is the rank (size of the largest hyperedge), and $\lambda$ is the connectivity of the hypergraph.
Calvin Beideman
,
Karthekeyan Chandrasekaran
,
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
×