Subcubic algorithms for Gomory–Hu tree in unweighted graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi · 2021
Every undirected graph G has a (weighted) cut-equivalent tree T, commonly named after Gomory and Hu who discovered it in 1961. Both T and G have the same node set, and for every node pair s,t, the minimum (s,t)-cut in T is also an exact minimum (s,t)-cut in G.