Intractability of min- and max-cut in streaming graphs
A PHP Error was encountered
Message: Undefined index: id
Line Number: 218
We show that the exact computation of a minimum or a maximum cut of a given graph G is out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n2) bits. This holds even if randomization is allowed.