Graph Sparsification in the Semi-streaming Model

A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations

H. Chernoff · 1952

Earlier work this paper cites.

Multi-terminal network flows

R. E. Gomory and T.C. Hu · 1961

Earlier work this paper cites.

Selection and Sorting with Limited Storage

J. Ian Munro and Mike Paterson · 1980

Earlier work this paper cites.

A faster algorithm for finding the minimum cut in a graph

Jianxiu Hao and James B. Orlin · 1992

Earlier work this paper cites.

Global min-cuts in rnc, and other ramifications of a simple min-out algorithm

David R. Karger · 1993

Earlier work this paper cites.

Random sampling in cut, flow, and network design problems

David R. Karger · 1994

Earlier work this paper cites.

Approximating s-t minimum cuts in O(n2) time

András A. Benczúr and David R. Karger · 1996

Cited alongside, same era.

A new approach to the minimum cut problem

David R. Karger and Clifford Stein · 1996

Cited alongside, same era.

Experimental study of minimum cut algorithms

Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein · 1997

Cited alongside, same era.

Computing on data streams, 1998

M. Henzinger, P. Raghavan, and S. Rajagopalan · 1998

Cited alongside, same era.

The Space Complexity of Approximating the Frequency Moments

Noga Alon, Yossi Matias, and Mario Szegedy · 1999

Cited alongside, same era.

Minimum cuts in near-linear time

David R. Karger · 2000

Cited alongside, same era.

On graph problems in a semi-streaming model

Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang · 2005

Later among the works it cites.

Finding Graph Matchings in Data Streams

Andrew McGregor · 2005

Later among the works it cites.

Trading off space for passes in graph streaming problems

Camil Demetrescu, Irene Finocchi, and Andrea Ribichini · 2006

Later among the works it cites.

Data streams: Algorithms and Applications

S. Muthukrishnan · 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.