Fetching the paper…
Reading the bibliography…
Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs.
Lower bound of network reliability
M. V. Lomonosov and V. Polesskii · 1972
Earlier work this paper cites.
On the structure of the system of minimum edge cuts in a graph
E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov · 1976
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Random sampling in graph optimization problems
D. R. Karger · 1995
Earlier work this paper cites.
A Simple Hypergraph Min Cut Algorithm
R. Klimmek and F. Wagner · 1996
Earlier work this paper cites.
Better random sampling algorithms for flows in undirected graphs
D. R. Karger · 1998
Earlier work this paper cites.
Random sampling in cut, flow, and network design problems
D. R. Karger · 1999
Earlier work this paper cites.
Randomized approximation schemes for cuts and flows in capacitated graphs
A. A. Benczúr and D. R. Karger · 2002
Earlier work this paper cites.
Optimal inapproximability results for Max-Cut and other 2-variable CSPs?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2004
Earlier work this paper cites.
Graph sparsification in the semi-streaming model
K. J. Ahn and S. Guha · 2009
Earlier work this paper cites.
Algorithms for Streaming Graphs
M. Zelke · 2009
Cited alongside, same era.
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
H. Dell and D. van Melkebeek · 2010
Cited alongside, same era.
Intractability of min- and max-cut in streaming graphs
M. Zelke · 2010
Cited alongside, same era.
A survey on streaming algorithms for massive graphs
J. Zhang · 2010
Cited alongside, same era.
Sparse sums of positive semidefinite matrices
M. K. de Carli Silva, N. J. A. Harvey, and C. M. Sato · 2011
Cited alongside, same era.
Open questions in data streams, property testing, and related topics
P. Indyk, A. McGregor, I. Newman, and K. Onak · 2011
Cited alongside, same era.
Single pass sparsification in the streaming model with edge deletions
A. Goel, M. Kapralov, and I. Post · 2012
Later among the works it cites.
On multiplicative
I. Newman and Y. Rabinovich · 2013
Later among the works it cites.
The sketching complexity of graph cuts
A. Andoni, R. Krauthgamer, and D. P. Woodruff · 2014
Closest in time.
High dimensional expanders, ramanujan complexes and topological overlapping
T. Kaufman, D. Kazhdan, and A. Lubotzky · 2014
Closest in time.
Streaming lower bounds for approximating MAX-CUT
M. Kapralov, S. Khanna, and M. Sudan · 2014
Closest in time.
Approximation algorithms for hypergraph small set expansion and small set vertex expansion
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Single pass spectral sparsification in dynamic streams
M. Kapralov, Y. T. Lee, C. Musco, C. Musco, and A. Sidford · 2011
Cited alongside, same era.
The streaming complexity of cycle counting, sorting by reversals, and other problems
W. Yu and E. Verbin · 2011
Cited alongside, same era.
Analyzing graph structure via linear measurements
K. J. Ahn, S. Guha, and A. McGregor · 2012
Cited alongside, same era.
Graph sketches: Sparsification, spanners, and subgraphs
K. J. Ahn, S. Guha, and A. McGregor · 2012
Cited alongside, same era.
Approximating s-t minimum cuts in
A. A. Benczúr and D. R. Karger
Cited in the paper.
Global min-cuts in
D. R. Karger
Cited in the paper.
A. Louis and Y. Makarychev · 2014
Closest in time.
Hypergraph Markov operators, eigenvalues and approximation algorithms
A. Louis · 2014
Closest in time.
Graph stream algorithms: A survey
A. McGregor · 2014
Closest in time.
Cyber security analysis of power networks by hypergraph cut algorithms
Y. Yamaguchi, A. Ogawa, A. Takeda, and S. Iwata · 2014
Closest in time.