Small stretch (α,β)-spanners in the streaming model

• Published in: Theoretical computer science 2009-08, Vol.410 (36), p.3406-3413
• Main Authors: Ausiello, Giorgio, Franciosa, Paolo G., Italiano, Giuseppe F.
• Format: Article
• Language: English
• Subjects: External memory; Graph algorithms; Graph spanners; Streaming algorithms
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2008.04.022

We present algorithms for computing small stretch (α,β)-spanners in the streaming model. An (α,β)-spanner of a graph G is a subgraph S⊆G such that for each pair of vertices the distance in S is at most α times the distance in G 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 m the current number of scanned edges and by n the current number of discovered vertices. 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(n1+1/k) edges and our algorithms use only O(n1+1/k) words of memory space. In case only Θ(n) internal memory is available, the same spanners can be computed using O(n1+1/k/B) external memory blocks, each of size B. Each edge/vertex is processed in O(1) amortized time, plus O(1/B) amortized block transfers.