Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System
Abstract
Let S=(V,f), be a symmetric submodular system. For two distinct elements s and l of V, let Γ(s,l) denote the set of all subsets of V which separate s from l. By using every Gomory Hu tree of S we can obtain an element of Γ(s,l) which has minimum value among all the elements of Γ(s,l). This tree can be constructed iteratively by solving |V|−1 minimum sl-separator problem. An ordered pair (s, l) is called a pendant pair of S if {l} is a minimum sl-separator. Pendant pairs of a symmetric submodular system play a key role in finding a minimizer of this system. In this paper, we obtain a Gomory Hu tree of a contraction of S with respect to some subsets of V only by using contraction in Gomory Hu tree of S. Furthermore, we obtain some pendant pairs of S and its contractions by using a Gomory Hu tree of S.
Origin | Files produced by the author(s) |
---|