Skip to main content

Computing Exact Minimum Cuts Without Knowing the Graph

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

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRubinstein, Aviad-
dc.contributor.authorSchramm, Tselil-
dc.contributor.authorWeinberg, S Matthew-
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.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.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

Files in This Item:
File Description SizeFormat 
ComputeExactMinCutsWithoutKnowingGraph.pdf580.88 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.