Space Complexity of Minimum Cut Problems in Single-Pass Streams

Matthew Ding, Alexandro Garces, Jason Li +4

We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…