Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
3
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
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
Cite
×