Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MIN-CUT:
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