Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting
2016 · (arXiv 2016)
Abstract
We present an improved proof that the incremental resparsification algorithm from Kelner and Levin (2013) generates a spectral sparsifier with high probability. Our key contribution involves rigorously handling dependencies between consecutive resparsifications through martingale inequalities, thereby addressing a gap in the original analysis.
PDF · arXiv preprint · bibtex · DOI