Small stretch spanners in the streaming model: New algorithms and experiments

We present deterministic algorithms for computing small stretch spanners in the streaming model. An (alpha, beta)-spanner of a graph G with n vertices is a subgraph S subset of G such that for each pair of vertices the distance in S is at most a times the distance in G plus beta. We assume that the graph is given as a stream of edges in arbitrary order, that the number of vertices and the number of edges are not known in advance and that only one pass over the data is allowed. In this model, we show how to compute a (k, k - 1)-spanner of an unweighted undirected graph, for k = 2, 3, in O(1) amortized processing time per edge/vertex. The computed (k, k - 1)-spanners have O(n(1+1/k)) edges and our algorithms use only O(n(1+1/k)) words of memory space. In case only theta(n) internal memory is available, our algorithms can be adapted to store some of the data structures in external memory. We complement our theoretical analysis with an experimental study that suggests that our approach can be of practical value.