Intractability of min- and max-cut in streaming graphs |
| |
Authors: | Mariano Zelke |
| |
Affiliation: | Institut für Informatik, Goethe-Universität, Frankfurt am Main, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Graph algorithms Streaming algorithms Intractability Min-cut Max-cut |
本文献已被 ScienceDirect 等数据库收录! |