Fetching the paper…
Reading the bibliography…
Given a weighted graph $G$ and an error parameter $\epsilon > 0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_{\epsilon}$ (containing O(n\log n) edges in expectation) with the following property: the weight of every cut in $G_{\epsilon}$ is within a factor of $(1\pm \epsilon)$ of the weight of the corresponding cut in $G$.
A reduction method for edge-connectivity in graphs
Wolfgang Mader · 1978
Earlier work this paper cites.
Konstruktion aller n-fach kantenzusammenhangenden di-graphen
Wolfgang Mader · 1982
Earlier work this paper cites.
A data structure for dynamic trees
Daniel Dominic Sleator and Robert Endre Tarjan · 1983
Earlier work this paper cites.
Random Walks and Electric Networks
Peter G. Doyle and Laurie J. Snell · 1984
Earlier work this paper cites.
Binomial random variate generation
Voratas Kachitvichyanukul and Bruce W. Schmeiser · 1988
Earlier work this paper cites.
On a theorem of Mader
András Frank · 1992
Earlier work this paper cites.
Computing edge-connectivity in multigraphs and capacitated graphs
Hiroshi Nagamochi and Toshihide Ibaraki · 1992
Earlier work this paper cites.
A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph
Hiroshi Nagamochi and Toshihide Ibaraki · 1992
Earlier work this paper cites.
Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm
David R. Karger · 1993
Cited alongside, same era.
Combinatorial Problems and Exercises, 2nd ed
László Lovász · 1993
Cited alongside, same era.
Random sampling in cut, flow, and network design problems
David R. Karger · 1994
Cited alongside, same era.
Using randomized sparsification to approximate minimum cuts
David R. Karger · 1994
Cited alongside, same era.
Approximating s-t
András A. Benczúr and David R. Karger · 1996
Cited alongside, same era.
Randomized Algorithms
R. Motwani and P. Raghavan · 1997
Cited alongside, same era.
Modern Graph Theory
Bela Bollobas · 1998
A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
David R. Karger · 1999
Later among the works it cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Later among the works it cites.
Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2006
Later among the works it cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Later among the works it cites.
Edge-splittings preserving local edge-connectivity of graphs
Zoltán Szigeti · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Beyond the flow decomposition barrier
Andrew V. Goldberg and Satish Rao · 1998
Cited alongside, same era.
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Later among the works it cites.
Graph partitioning using single commodity flows
Rohit Khandekar, Satish Rao, and Umesh V. Vazirani · 2009
Later among the works it cites.
Breaking the multicommodity flow barrier for O ( log n ) O(\sqrt{\log n}) -approximations to sparsest cut
Jonah Sherman · 2009
Later among the works it cites.