All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
By: Yotam Kenneth-Mordoch, Robert Krauthgamer
Potential Business Impact:
Finds the weakest links in any network.
We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph $G=(V,E)$ with $n$ vertices, our randomized algorithm constructs a Gomory-Hu tree of $G$, and thus solves the all-pairs minimum cut problem, using $\tilde{O}(n^{7/4})$ cut queries.
Similar Papers
Minimum $s$--$t$ Cuts with Fewer Cut Queries
Data Structures and Algorithms
Finds the weakest link in a network faster.
Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
Data Structures and Algorithms
Finds weakest points in networks faster.
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Data Structures and Algorithms
Finds best ways to cut networks, faster.