In combinatorial optimization, the Gomory–Hu tree[1] of an undirected graph with capacities is a weighted tree that represents the minimum s-t cuts for all s-t pairs in the graph.
The Gomory–Hu tree can be constructed in |V| − 1 maximum flow computations.
It is named for Ralph E. Gomory and T. C. Hu.
where Gomory–Hu Algorithm Using the submodular property of the capacity function c, one has
for some p ∈ P, q ∈ Q throughout the algorithm, one makes use of the following lemma, The lemma can be used again repeatedly to show that the output T satisfies the properties of a Gomory–Hu Tree.
Gusfield's algorithm can be used to find a Gomory–Hu tree without any vertex contraction in the same running time-complexity, which simplifies the implementation of constructing a Gomory–Hu Tree.
[2] Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm, and performed an experimental evaluation and comparison.
[3] Cohen et al. report results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively.
[4] In planar graphs, the Gomory–Hu tree is dual to the minimum weight cycle basis, in the sense that the cuts of the Gomory–Hu tree are dual to a collection of cycles in the dual graph that form a minimum-weight cycle basis.