Fetching the paper…
Reading the bibliography…
We give an algorithm to find a minimum cut in an edge-weighted directed graph with $n$ vertices and $m$ edges in $\tilde O(n\cdot \max(m^{2/3}, n))$ time.
Maximal flow through a network
L. R. Ford and D. R. Fulkerson · 1956
Earlier work this paper cites.
Edge-disjoint branchings
Jack Edmonds · 1973
Earlier work this paper cites.
An algorithm for finding the edge connectivity of graphs
V. D. Podderyugin · 1973
Earlier work this paper cites.
Network flow and testing graph connectivity
Shimon Even and Robert Endre Tarjan · 1975
Earlier work this paper cites.
Bottlenecks and edge connectivity in unsymmetrical networks
Claus-Peter Schnorr · 1979
Earlier work this paper cites.
Finding the vertex connectivity of graphs
Zvi Galil · 1980
Earlier work this paper cites.
An o ( n log 2 n ) o(n\log^{2}n) algorithm for the k th longest path in a tree with applications to location problems
N. Megiddo, Arie Tamir, Eitan Zemel, and Ramaswamy Chandrasekaran · 1981
Earlier work this paper cites.
Efficient algorithms for finding minimum spanning tree in undirected and directed graphs
Harold Gabow, Zvi Galil, Thomas Spencer, and Robert Tarjan · 1986
Earlier work this paper cites.
A new approach to the maximum-flow problem
Andrew V. Goldberg and Robert Endre Tarjan · 1988
Earlier work this paper cites.
Finding the edge connectivity of directed graphs
Yishay Mansour and Baruch Schieber · 1989
Earlier work this paper cites.
Directed s s – t t numberings, rubber bands, and testing digraph k k -vertex connectivity
Joseph Cheriyan and John H. Reif · 1994
Cited alongside, same era.
A faster algorithm for finding the minimum cut in a directed graph
Jianxiu Hao and James B. Orlin · 1994
Cited alongside, same era.
A matroid approach to finding edge connectivity and packing arborescences
H.N. Gabow · 1995
Cited alongside, same era.
Randomized rounding without solving the linear program
Neal E. Young · 1995
Cited alongside, same era.
Computing vertex connectivity: New bounds from old techniques
Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow · 2000
Cited alongside, same era.
Minimum cuts in near-linear time
David R Karger · 2000
Cited alongside, same era.
Bipartite matching in nearly-linear time on moderately dense graphs
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2020
Later among the works it cites.
Sparsification of balanced directed graphs
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun · 2021
Closest in time.
Minimum cuts in directed graphs via √ \surd n max-flows
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, and Thatchaphol Saranurak · 2021
Closest in time.
Faster algorithms for rooted connectivity in directed graphs
Chandra Chekuri and Kent Quanrud · 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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Breaking quadratic time for small vertex connectivity and an approximation scheme
Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai · 2019
Cited alongside, same era.
Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms
Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai · 2020
Cited alongside, same era.
Minimum cut in o(m log 2 n) time
Pawel Gawrychowski, Shay Mozes, and Oren Weimann · 2020
Cited alongside, same era.
Weighted min-cut: sequential, cut-query, and streaming algorithms
Sagnik Mukhopadhyay and Danupon Nanongkai · 2020
Cited alongside, same era.
A note on a recent algorithm for minimum cut
Pawel Gawrychowski, Shay Mozes, and Oren Weimann · 2021
Closest in time.
Work-optimal parallel minimum cuts for non-sparse graphs
Andrés López-Martínez, Sagnik Mukhopadhyay, and Danupon Nanongkai · 2021
Closest in time.
Vertex connectivity in poly-logarithmic max-flows, 2021
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai · 2021
Closest in time.
Fast approximations for rooted connectivity in weighted directed graphs
Kent Quanrud · 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
Closest in time.