Single Pass Spectral Sparsification in Dynamic Streams

Preprint English OPEN
Kapralov, Michael; Lee, Yin Tat; Musco, Cameron; Musco, Christopher; Sidford, Aaron;
  • Subject: Computer Science - Data Structures and Algorithms
    arxiv: Computer Science::Data Structures and Algorithms

We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph G, our algorithm maintains a randomized linear sketch o... View more