We present algorithms for computing small stretch -spanners in the streaming model. An -spanner of a graph is a subgraph such that for each pair of vertices the distance in is at most times the distance in plus . We assume that the graph is given as a stream of edges and vertices, and that only one pass over the data is allowed. Furthermore, the number of vertices and edges are not known in advance. We denote by the current number of scanned edges and by the current number of discovered vertices. In this model we show how to compute a -spanner of an unweighted undirected graph, for , in amortized processing time per edge/vertex. The computed -spanners have edges and our algorithms use only words of memory space. In case only internal memory is available, the same spanners can be computed using external memory blocks, each of size . Each edge/vertex is processed in amortized time, plus amortized block transfers.
Partially supported by the Italian Ministry of University and Research under Project MAINSTREAM “Algorithms for Massive Information Structures and Data Streams” and by EU project 215270 FRONTS.