Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

A note on the maximum flow through a network

P. Elias, A. Feinstein, and C. E. Shannon · 1956

Earlier work this paper cites.

Maximal flow through a network

L. R. Ford and D. R. Fulkerson · 1956

Earlier work this paper cites.

Network flow and testing graph connectivity

S. Even and R. E. Tarjan · 1975

Earlier work this paper cites.

Network flows

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin · 1989

Earlier work this paper cites.

Applications of network optimization

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, and M. R. Reddy · 1995

Earlier work this paper cites.

Fast approximation algorithms for fractional packing and covering problems

S. A. Plotkin, D. B. Shmoys, and É.. Tardos · 1995

Earlier work this paper cites.

Approximating s-t minimum cuts in Õ ( n 2 ) (n^{2}) time

A. A. Benczúr and D. R. Karger · 1996

Cited alongside, same era.

Modern Graph Theory

B. Bollobas · 1998

Cited alongside, same era.

Beyond the flow decomposition barrier

A. V. Goldberg and S. Rao · 1998

Cited alongside, same era.

Better random sampling algorithms for flows in undirected graphs

D. R. Karger · 1998

Cited alongside, same era.

Randomized approximation schemes for cuts and flows in capacitated graphs

A. A. Benczúr and D. R. Karger · 2002

Cited alongside, same era.

Combinatorial Optimization, Volume A

A. Schrijver · 2003

Cited alongside, same era.

The multiplicative weights update method: A meta-algorithm and applications

S. Arora, E. Hazan, and S. Kale

Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems

D. A. Spielman and S.-H. Teng · 2006

Later among the works it cites.

Faster approximate lossy generalized flow via interior point algorithms

S. I. Daitch and D. A. Spielman · 2008

Later among the works it cites.

Breaking the multicommodity flow barrier for O ⁡ ( log ⁡ n ) {O}\left(\sqrt{\log n}\right) -approximations to sparsest cut

J. Sherman · 2009

Later among the works it cites.

Approaching optimality for solving SDD systems

I. Koutis, G. L. Miller, and R. Peng · 2010

Closest in time.

Fast approximation algorithms for cut-based problems in undirected graphs

A. Mądry · 2010

Closest in time.