Sagnik Mukhopadhyay

activity

20152026

most citedWeighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

38 citations · 53 across the 13 of their papers we have counts for

collaborators

Showing 2020Show all

2 papers · 1 filter

cs.DS2020

Faster connectivity in low-rank hypergraphs via expander decomposition

Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay +1

We design an algorithm for computing connectivity in hypergraphs which runs in time $O^_{r} (p + min {λ^{\frac{r - 3}{r - 1}} n^{2}, n^{r} / λ^{r / (r - 1)}})$ (the $O^_{r} (\cdot)$ hides th…

cs.DS2020

Distributed Weighted Min-Cut in Nearly-Optimal Time

Michal Dory, Yuval Efron, Sagnik Mukhopadhyay +1

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], ther…