Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting
Not on the map. Why?
Abstract (arXiv)
We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 13 Sep 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.