View article

In this paper we study graph problems in the dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require space, where n is the number of vertices, existing works mainly focused on designing space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e.g., n is huge or the graph is sparse). In this work, we give single-pass algorithms beating this space barrier for two classes of problems. We present o(n) space algorithms for estimating the number of connected components with additive error of a general graph and -approximating the weight of the minimum spanning tree of a connected graph with bounded edge weights, for any small constant . The latter improves upon the previous space algorithm given by Ahn et al. (SODA 2012) for the …