Fetching the paper…
Reading the bibliography…
An $s{\operatorname{-}}t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$.
Maximal flow through a network
Lester R. Ford and Delbert R. Fulkerson · 1956
Earlier work this paper cites.
A quantum algorithm for finding the minimum
Christoph Dürr and Peter Høyer · 1996
Earlier work this paper cites.
Beyond the flow decomposition barrier
Andrew V. Goldberg and Satish Rao · 1998
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2002
Earlier work this paper cites.
Lower bounds for local search by quantum arguments
Scott Aaronson · 2006
Earlier work this paper cites.
Quantum algorithms for matching and network flows
Andris Ambainis and Robert Špalek · 2006
Earlier work this paper cites.
Lower bounds for randomized and quantum query complexity using kolmogorov arguments
Sophie Laplante and Frédéric Magniez · 2008
Earlier work this paper cites.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Mądry, Daniel A. Spielman, and Shang-Hua Teng · 2011
Earlier work this paper cites.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Mądry · 2013
Cited alongside, same era.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2013
Cited alongside, same era.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Cited alongside, same era.
Path finding methods for linear programming: Solving linear programs in O ~ ( rank ) \widetilde{O}(\sqrt{\text{rank}}) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Cited alongside, same era.
Randomized approximation schemes for cuts and flows in capacitated graphs
András A. Benczúr and David R. Karger · 2015
Cited alongside, same era.
Quantum speedup for graph sparsification, cut approximation and Laplacian solving
Simon Apers and Ronald de Wolf · 2020
Later among the works it cites.
Faster energy maximization for faster maximum flow
Yang P. Liu and Aaron Sidford · 2020
Later among the works it cites.
All classical adversary methods are equivalent for total functions
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, and Aleksejs Zajakins · 2021
Closest in time.
Quantum complexity of minimum cut
Simon Apers and Troy Lee · 2021
Closest in time.
Fully dynamic electrical flows: Sparse maxflow faster than Goldberg-Rao
Yu Gao, Yang P. Liu, and Richard Peng · 2021
Closest in time.
Minimum cost flows, MDPs, and ℓ 1 \ell_{1} -regression in nearly linear time for dense instances
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2021
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Approximate undirected maximum flows in O ( m polylog ( n ) ) O(m\,\mathrm{polylog}(n)) Time
Richard Peng · 2016
Cited alongside, same era.
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg · 2018
Cited alongside, same era.
Coordinate methods for accelerating ℓ ∞ \ell_{\infty} regression and faster approximate maximum flow
Aaron Sidford and Kevin Tian · 2018
Cited alongside, same era.
Closest in time.
Maximum flow and minimum-cost flow in almost-linear time
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva · 2022
Closest in time.