Elsevier

Theoretical Computer Science

Volume 410, Issue 36, 31 August 2009, Pages 3406-3413
Theoretical Computer Science

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

https://doi.org/10.1016/j.tcs.2008.04.022Get rights and content
Under an Elsevier user license
open archive

Abstract

We present algorithms for computing small stretch (α,β)-spanners in the streaming model. An (α,β)-spanner of a graph G is a subgraph SG 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,k1)-spanner of an unweighted undirected graph, for k=2,3, in O(1) amortized processing time per edge/vertex. The computed (k,k1)-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.

Keywords

Graph algorithms
Graph spanners
Streaming algorithms
External memory

Cited by (0)

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.