Intractability of min- and max-cut in streaming graphs

Article ID	Journal	Published Year	Pages	File Type
10332020	Information Processing Letters	2011	6 Pages	PDF

Abstract

âº A minimum/maximum cut cannot be computed exactly by a one-pass streaming algorithm. âº This holds for deterministic and randomized algorithms. âº Tools of communication complexity are utilized.

Keywords

Streaming algorithms Graph algorithms Max-Cut Min-cut Intractability

Related Topics

Physical Sciences and Engineering Computer Science Computational Theory and Mathematics

Preview

Intractability of min- and max-cut in streaming graphs

Authors

Mariano Zelke,