A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of ( 1 ± ϵ ) . This paper considers computing cut sparsifiers of weighted graphs of size O ( n log ( n ) / ϵ ... ...
