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