Single pass sparsification in the streaming model with edge deletions

Details Single pass sparsification in the streaming model with edge deletions Single pass sparsification in the streaming model with edge deletions

2012-03-22

arxiv.org/abs/1203.4900v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions either required multiple passes or were unable to handle edge deletions. We use $\tilde{O}(1/\e^2)$ time for each stream update and $\tilde{O}(n/\e^2)$ time to construct a sparsifier. Our $\e$-sparsifiers have $O(n\log^3 n/\e^2)$ edges. The main tools behind our result are an application of sketching techniques of Ahn et al.[SODA'12] to estimate edge connectivity together with a novel application of sampling with limited independence and sparse recovery to produce the edges of the sparsifier.

Affiliated with

Also associated with

No associations

Rating

Single pass sparsification in the streaming model with edge deletions 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 Single pass sparsification in the streaming model with edge deletions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single pass sparsification in the streaming model with edge deletions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-381383