Given a graph of n nodes, the Gomory-Hu cut tree represents the n(n−1)/2 minimum cuts between all pairs of nodes with only n−1 links of the cut tree. The Gomory-Hu method utilizes the existence of the n−1 noncrossing minimum cuts. A node contraction is used to reduce the complexity of the graph and to ensure that a minimum cut routine generates noncrossing cuts. The node contraction and the related data structure complicate the coding of the method, however. In many applications, the complexity of the coding hinders the adoption of this nice approach.

Gusfield elegantly simplifies the coding to construct the Gomory-Hu cut tree. He shows that for each crossing minimum cut, we can derive a corresponding noncrossing minimum cut by a simple neighborhood search. Therefore, the construction of the cut tree does not need to avoid the crossing cuts and thus does not have to perform the node contraction; this dramatically reduces the complexity of the coding. The proposed approach can easily be implemented by adding less than ten simple lines of code to any minimum cut routine.

A recent paper by Cheng and Hu proposes an ancestor tree that represents the n(n−1)/2 minimum cuts for any arbitrary cost function of the cuts [1]. The method does not depend on the existence of the noncrossing cuts. The algorithm and its application can also be found in Gusfield[2].