Gomory–Hu tree

In combinatorial optimization, the Gomory–Hu tree 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.

Let G = ((V_G, E_G), c) be an undirected graph with c(u,v) being the capacity of the edge (u,v) respectively.

Then T is said to be a Gomory–Hu tree of G if

where

Gomory–Hu Algorithm

Using the submodular property of the capacity function c, one has

Then it can be shown that the minimum s-t cut in G' is also a minimum s-t cut in G for any s, t ∈ X.

To show that for all (P, Q) ∈ E_T, w(P,Q) = λ_pq 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.

The following is a simulation of the Gomory–Hu's algorithm, where

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.

Andrew V. Goldberg and K. Tsioutsiouliklis implemented the Gomory-Hu algorithm and Gusfield algorithm. Experimental results comparing these algorithms are reported in Source code is available here.

Cohen et al. reports results on two parallel implementations of Gusfield's algorithm using OpenMP and MPI, respectively. Source code of these implementations is available here: Parallel Cut Tree Algorithms Page. (broken link)

The Gomory–Hu tree was introduced by R. E. Gomory and T. C. Hu in 1961.

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.

...
Wikipedia