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.
Let be an undirected graph with being the capacity of the edge respectively.
Then T is said to be a Gomory–Hu tree of G, if for each
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 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. [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. [5]
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)
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.
Let be an undirected graph with being the capacity of the edge respectively.
Then T is said to be a Gomory–Hu tree of G, if for each
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 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. [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. [5]
{{
cite conference}}
: CS1 maint: multiple names: authors list (
link)