# Computing Exact Minimum Cuts Without Knowing the Graph

## Author(s): Rubinstein, Aviad; Schramm, Tselil; Weinberg, S Matthew

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1v841
DC FieldValueLanguage
dc.contributor.authorSchramm, Tselil-
dc.contributor.authorWeinberg, S Matthew-
dc.date.accessioned2021-10-08T19:47:58Z-
dc.date.available2021-10-08T19:47:58Z-
dc.date.issued2018en_US
dc.identifier.citationRubinstein, Aviad, Tselil Schramm, and S. Matthew Weinberg. "Computing Exact Minimum Cuts Without Knowing the Graph." In 9th Innovations in Theoretical Computer Science Conference (ITCS) (2018): 39:1-39:16. doi:10.4230/LIPIcs.ITCS.2018.39en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1v841-
dc.description.abstractWe give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S \subset V, the oracle returns the size of the cut between S and V \ S. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while learning the graph requires ~{\Theta}(n^2) queries).en_US
dc.format.extent39:1 - 39:16en_US
dc.language.isoen_USen_US
dc.relation.ispartof9th Innovations in Theoretical Computer Science Conference (ITCS)en_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleComputing Exact Minimum Cuts Without Knowing the Graphen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.ITCS.2018.39-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat