Expander Decomposition in Dynamic Streams

Arnold Filtser, Michael Kapralov, Mikhail Makarov

In this paper we initiate the study of expander decompositions of a graph $G=(V,E)$ in the streaming model of computation. The goal is to find a partitioning $\mathcal{C}$ of vert…