A General Framework for Graph Sparsification
A General Framework for Graph Sparsification
We present a general framework for constructing cut sparsifiers in undirected graphs---weighted subgraphs for which every cut has the same weight as the original graph, up to a multiplicative factor of $(1 \pm \epsilon)$. Using this framework, we simplify, unify, and improve upon previous sparsification results. As simple instantiations of …