Faster Streaming algorithms for graph spanners
<|reference_start|>Faster Streaming algorithms for graph spanners: Given an undirected graph $G=(V,E)$ on $n$ vertices, $m$ edges, and an integer $t\ge 1$, a subgraph $(V,E_S)$, $E_S\subseteq E$ is called a $t$-spanner if for any pair of vertices $u,v \in V$, the distance between them in the subgraph is at most $t$ times the actual distance. We present streaming algorithms for computing a $t$-spanner of essentially optimal size-stretch trade offs for any undirected graph.   Our first algorithm is for the classical streaming model and works for unweighted graphs only. The algorithm performs a single pass on the stream of edges and requires $O(m)$ time to process the entire stream of edges. This drastically improves the previous best single pass streaming algorithm for computing a $t$-spanner which requires $\theta(mn^{\frac{2}{t}})$ time to process the stream and computes spanner with size slightly larger than the optimal.   Our second algorithm is for {\em StreamSort} model introduced by Aggarwal et al. [FOCS 2004], which is the streaming model augmented with a sorting primitive. The {\em StreamSort} model has been shown to be a more powerful and still very realistic model than the streaming model for massive data sets applications. Our algorithm, which works of weighted graphs as well, performs $O(t)$ passes using $O(\log n)$ bits of working memory only.   Our both the algorithms require elementary data structures.<|reference_end|>
@article{baswana2006faster,
    title={Faster Streaming algorithms for graph spanners},
    author={Surender Baswana},
    journal={arXiv preprint arXiv:cs/0611023},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0611023},
    primaryClass={cs.DS}
}