Single pass sparsification in the streaming model with edge deletions

Ashish Goel, Michael Kapralov, Ian Post

In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions e…