Fetching the paper…
Reading the bibliography…
We present new approaches to constructing graph sparsifiers --- weighted subgraphs for which every cut has the same value as the original graph, up to a factor of $(1 \pm \epsilon)$.
The dissection of rectangles into squares
R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte · 1940
Earlier work this paper cites.
The average impedance of an electric network
R. M. Foster · 1949
Earlier work this paper cites.
The structure of a system of minimal edge cuts of a graph
E. A. Dinic, A. V. Karzanov, and M. V. Lomonosov · 1976
Earlier work this paper cites.
The complexity of nonuniform random number generation
D.E. Knuth and A.C. Yao · 1976
Earlier work this paper cites.
A reduction method for edge-connectivity in graphs
Wolfgang Mader · 1978
Earlier work this paper cites.
Non-Uniform Random Variate Generation
Luc Devroye · 1986
Earlier work this paper cites.
Computing edge-connectivity in multiple and capacitated graphs
Toshihide Ibaraki · 1990
Earlier work this paper cites.
Random walks and the effective resistance of networks
Prasad Tetali · 1991
Earlier work this paper cites.
Balanced matroids
T. Feder and M. Mihail · 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
Earlier work this paper cites.
The connectivity carcass of a vertex subset in a graph and its incremental maintenance
Yefim Dinitz and Alek Vainshtein · 1994
Earlier work this paper cites.
Random sampling in cut, flow, and network design problems
David R. Karger · 1994
Earlier work this paper cites.
Approximate s s - t t min-cuts in O ~ ( n 2 ) \tilde{O}(n^{2}) time
András A. Benczúr and David R. Karger · 1996
Cited alongside, same era.
Two algorithms for unranking arborescences
Charles J. Colbourn, Wendy J. Myrvold, and Eugene Neufeld · 1996
Cited alongside, same era.
A new approach to the minimum cut problem
David R. Karger and Clifford Stein · 1996
Cited alongside, same era.
Random walks on graphs: A survey
László Lovász · 1996
Cited alongside, same era.
Cut structures and randomized algorithms in edge-connectivity problems
András A. Benczúr · 1997
Cited alongside, same era.
Modern Graph Theory
Béla Bollobás · 1998
Cited alongside, same era.
Concentration
Colin McDiarmid · 1998
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Later among the works it cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Later among the works it cites.
Spectral sparsification of graphs, 2008
Daniel A. Spielman and Shang-Hua Teng · 2008
Later among the works it cites.
Twice-Ramanujan sparsifiers
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava · 2009
Later among the works it cites.
A quick proof for the cactus representation of mincuts
Tamás Fleiner and András Frank · 2009
Later among the works it cites.
Expanders via random spanning trees
Navin Goyal, Luis Rademacher, and Santosh Vempala · 2009
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.
Coverings and structure of crossing families
Tamás Fleiner and Tibor Jordán · 1999
Cited alongside, same era.
Random sampling in cut, flow, and network design problems
David R. Karger · 1999
Cited alongside, same era.
The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. odd case
Yefim Dinitz and Alek Vainshtein · 2000
Cited alongside, same era.
Randomized approximation schemes for cuts and flows in capacitated graphs, 2002
András A. Benczúr and David R. Karger · 2002
Cited alongside, same era.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Cited alongside, same era.
Faster generation of random spanning trees
Jonathan A. Kelner and Aleksander Madry · 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.
A general framework for graph sparsification, April 2010
Ramesh Hariharan and Debmalya Panigrahi · 2010
Closest in time.
Approaching optimality for solving SDD systems, 2010
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Closest in time.
Probability on Trees and Networks
Russell Lyons and Yuval Peres · 2010
Closest in time.
Algorithms, graph theory, and linear equations
Daniel A. Spielman · 2010
Closest in time.