Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with min-cut:
TR20-108 | 19th July 2020
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Query Complexity of Global Minimum Cut

In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like \textsc{Degree}, \textsc{Neighbor}, and \textsc{Adjacency} queries.

Given $\epsilon \in (0,1)$, ... more >>>

ISSN 1433-8092 | Imprint