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. © 2008 Elsevier B.V. All rights reserved.

Small stretch (α, β)-spanners in the streaming model / Ausiello, Giorgio; Franciosa, Paolo Giulio; Italiano, GIUSEPPE FRANCESCO. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 410:36(2009), pp. 3406-3413. [10.1016/j.tcs.2008.04.022]

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

AUSIELLO, Giorgio;FRANCIOSA, Paolo Giulio;ITALIANO, GIUSEPPE FRANCESCO
2009

Abstract

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. © 2008 Elsevier B.V. All rights reserved.
2009
external memory; graph algorithms; graph spanners; streaming algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
Small stretch (α, β)-spanners in the streaming model / Ausiello, Giorgio; Franciosa, Paolo Giulio; Italiano, GIUSEPPE FRANCESCO. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 410:36(2009), pp. 3406-3413. [10.1016/j.tcs.2008.04.022]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/229716
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact