Abstract This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners
in the data streaming model, where 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
β. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting.
We compare experimentally the randomized algorithms proposed by Baswana (
http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0611023) and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007),
Wroclaw, Poland, pp. 716–727, 9–13 July
2007) for general stretch factors with the deterministic algorithm presented by Ausiello
et al. (In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track, Eilat,
Israel, 8–10 October 2007. LNCS, vol. 4698, pp. 605–617,
2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the
input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently
from the algorithm in Ausiello
et al., the algorithms in Baswana (
http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0611023) and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw,
Poland, pp. 716–727, 9–13 July
2007) need to know in advance the number of vertices in the graph.
The results of our experimental investigation on several input families confirm that all these algorithms are very efficient
in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable
by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of
interest in practice, and that the algorithm by Ausiello et al. tends to produce spanners of better quality than the algorithms by Baswana and Elkin, while still using a comparable amount
of time and space resources.