Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Project
Light
Dark
Automatic
Graph algorithm
Finding a Small Vertex Cut on Distributed Networks
We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer $\kappa$, our algorithm can, with high probability, either find $\kappa$ vertices whose removal disconnects the network or return that such $\kappa$ vertices do not exist.
Yonggang Jiang
,
Sagnik Mukhopadhyay
Cut Query Algorithms with Star Contraction
We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge connectivity with $O(n)$ cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with $\tilde O(\sqrt{n})$ cut queries.
Simon Apers
,
Yuval Efron
,
Pawel Gawrychowski
,
Troy Lee
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
Nearly Optimal Communication and Query Complexity of Bipartite Matching
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models.
Joakim Blikstad
,
Jan van den Brand
,
Yuval Efron
,
Sagnik Mukhopadhyay
,
Danupon Nanongkai
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
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
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
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
Cite
×