Dynamic Graph Stream Algorithms in $o(n)$ Space

Zengfeng Huang, Pan Peng

In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require $\Omega (n)$…