Faster Streaming algorithms for graph spanners
| dc.creator | Baswana, Surender | |
| dc.date | 2006-11-06 | |
| dc.date.accessioned | 2026-07-07T07:31:39Z | |
| dc.date.available | 2026-07-07T07:31:39Z | |
| dc.description | Given an undirected graph $G=(V,E)$ on $n$ vertices, $m$ edges, and an integer $t\ge 1$, a subgraph $(V,E_S)$, $E_S\subseteq E$ is called a $t$-spanner if for any pair of vertices $u,v \in V$, the distance between them in the subgraph is at most $t$ times the actual distance. We present streaming algorithms for computing a $t$-spanner of essentially optimal size-stretch trade offs for any undirected graph. Our first algorithm is for the classical streaming model and works for unweighted graphs only. The algorithm performs a single pass on the stream of edges and requires $O(m)$ time to process the entire stream of edges. This drastically improves the previous best single pass streaming algorithm for computing a $t$-spanner which requires $θ(mn^{\frac{2}{t}})$ time to process the stream and computes spanner with size slightly larger than the optimal. Our second algorithm is for {\em StreamSort} model introduced by Aggarwal et al. [FOCS 2004], which is the streaming model augmented with a sorting primitive. The {\em StreamSort} model has been shown to be a more powerful and still very realistic model than the streaming model for massive data sets applications. Our algorithm, which works of weighted graphs as well, performs $O(t)$ passes using $O(\log n)$ bits of working memory only. Our both the algorithms require elementary data structures. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0611023 | |
| dc.identifier | http://arxiv.org/abs/cs/0611023 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/118831 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Faster Streaming algorithms for graph spanners | |
| dc.type | text |