Fetching the paper…
Reading the bibliography…
We present an $\tilde{O}\left(m^{\frac{10}{7}}U^{\frac{1}{7}}\right)$-time algorithm for the maximum $s$-$t$ flow problem and the minimum $s$-$t$ cut problem in directed graphs with $m$ arcs and largest integer capacity $U$.
Über matrizen aus nicht negativen elementen
F. G. Frobenius · 1912
Earlier work this paper cites.
Vonalrendszerek és determinánsok
D. König · 1915
Earlier work this paper cites.
Über graphen und ihre anwendung auf determinantentheorie und mengenlehre
D. König · 1916
Earlier work this paper cites.
Über zerlegbare determinanten
F. G. Frobenius · 1917
Earlier work this paper cites.
Sur un probléme de la théorie générale des ensembles et la théorie des graphes
D. König · 1923
Earlier work this paper cites.
Matrixok kombinatorius tulajdonságairól
J. Egerváry · 1931
Earlier work this paper cites.
Graphok és matrixok
D. König · 1931
Earlier work this paper cites.
The factorization of linear graphs
W. T. Tutte · 1947
Earlier work this paper cites.
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.
Paths, trees, and flowers
J. Edmonds · 1965
Earlier work this paper cites.
Theoretical improvements in algorithmic efficiency for network flow problems
J. Edmonds and R. M. Karp · 1972
Earlier work this paper cites.
An n 5 / 2 n^{5/2} algorithm for maximum matchings in bipartite graphs
J. Hopcroft and R. Karp · 1973
Earlier work this paper cites.
O nakhozhdenii maksimal’nogo potoka v setyakh spetsial’nogo vida i nekotorykh prilozheniyakh
A. V. Karzanov · 1973
Earlier work this paper cites.
Triangular factorization and inversion by fast matrix multiplication
J. R. Bunch and J. E. Hopcroft · 1974
Earlier work this paper cites.
Network flow and testing graph connectivity
S. Even and R. E. Tarjan · 1975
Earlier work this paper cites.
On determinants, matchings and random algorithms
L. Lovász · 1979
Earlier work this paper cites.
An O ( | V | ⋅ | E | ) {O}(\sqrt{|V|}\cdot|E|) algoithm for finding maximum matching in general graphs
S. Micali and V. V. Vazirani · 1980
Earlier work this paper cites.
Matching Theory
L. Lovász and D. M. Plummer · 1986
Earlier work this paper cites.
Maximum matchings in general graphs through randomization
M. O. Rabin and V. V. Vazirani · 1989
Earlier work this paper cites.
Matrix multiplication via arithmetic progressions
D. Coppersmith and S. Winograd · 1990
Cited alongside, same era.
Computing a maximum cardinality matching in a bipartite graph in time O ( n 1.5 m / log n ) {O}(n^{1.5}\sqrt{m/\log n})
H. Alt, N. Blum, K. Mehlhorn, and M. Paul · 1991
Cited alongside, same era.
Faster scaling algorithms for general graph matching problems
H. N. Gabow and R. E. Tarjan · 1991
Cited alongside, same era.
Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners
P. M. Vaidya · 1991
Cited alongside, same era.
Network flows: theory, algorithms, and applications
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin · 1993
Cited alongside, same era.
A faster deterministic maximum flow algorithm
V. King, S. Rao, and R. Tarjan · 1994
Algebraic algorithms for matching and matroid problems
N. J. A. Harvey · 2009
Later among the works it cites.
Breaking the multicommodity flow barrier for O ( log n ) {O}(\sqrt{\log n}) -approximations to sparsest cuts
J. Sherman · 2009
Later among the works it cites.
Approaching optimality for solving SDD systems
I. Koutis, G. L. Miller, and R. Peng · 2010
Later among the works it cites.
Fast approximation algorithms for cut-based problems in undirected graphs
A. Mądry · 2010
Later among the works it cites.
Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
P. Christiano, J. Kelner, A. Mądry, D. Spielman, and S.-H. Teng · 2011
Later among the works it cites.
A nearly m log n m\log n -time solver for SDD linear systems
I. Koutis, G. L. Miller, and R. Peng · 2011
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
V. V. Vazirani · 1994
Cited alongside, same era.
Applications of Network Optimization
R. K. Ahuja, T. L. Magnanti, J. B. Orlin, and M. R. Reddy · 1995
Cited alongside, same era.
Clique partitions, graph compression and speeding-up algorithms
T. Feder and R. Motwani · 1995
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.
On the history of the transportation and maximum flow problems
A. Schrijver · 2002
Cited alongside, same era.
Later among the works it cites.
From Graphs to Matrices, and Back: New Techniques for Graph Algorithms
A. Mądry · 2011
Later among the works it cites.
The multiplicative weights update method: a meta-algorithm and applications
S. Arora, E. Hazan, and S. Kale · 2012
Later among the works it cites.
Multiplying matrices faster than Coppersmith-Winograd
V. Vassilevska Williams · 2012
Later among the works it cites.
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu · 2013
Later among the works it cites.
A new approach to computing maximum flows using electrical flows
Y. T. Lee, S. Rao, and N. Srivastava · 2013
Later among the works it cites.
Navigating central path with electrical flows: from flows to matchings, and back
A. Mądry · 2013
Later among the works it cites.
Max flows in O(nm) time, or better
J. B. Orlin · 2013
Later among the works it cites.
Nearly maximum flows in nearly linear time
J. Sherman · 2013
Later among the works it cites.
Solving SDD linear systems in nearly m log 1 / 2 n \log^{1/2}n time
M. B. Cohen, R. Kyng, G. L. Miller, J. W. Pachocki, R. Peng, A. B. Rao, and S. C. Xu · 2014
Later among the works it cites.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford · 2014
Later among the works it cites.
Path finding methods for linear programming: Solving linear programs in O ~ ( r a n k ) \tilde{{O}}(\sqrt{rank}) iterations and faster algorithms for maximum flows
Y. T. Lee and A. Sidford · 2014
Later among the works it cites.
Sparsified cholesky and multigrid solvers for connection laplacians
R. Kyng, Y. T. Lee, R. Peng, S. Sachdeva, and D. A. Spielman · 2016
Closest in time.
Approximate Gaussian elimination for Laplacians: Fast, sparse, and simple
R. Kyng and S. Sachdeva · 2016
Closest in time.
Approximate undirected maximum flows in O ( m p o l y l o g ( n ) ) {O}(mpolylog(n)) time
R. Peng · 2016
Closest in time.