On the Streaming Complexity of Expander Decomposition

Yu Chen, Michael Kapralov, Mikhail Makarov +1

In this paper we study the problem of finding $(\epsilon ,\varphi )$-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions…