Computer Science – Data Structures and Algorithms
Scientific paper
2006-11-06
Computer Science
Data Structures and Algorithms
16 pages
Scientific paper
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 $\theta(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.
No associations
LandOfFree
Faster Streaming algorithms for graph spanners does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster Streaming algorithms for graph spanners, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Streaming algorithms for graph spanners will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-297209