Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System
Abstract
Let $\mathcal {S}=(V, f),$ be a symmetric submodular system. For two distinct elements s and l of V, let $\varGamma (s, l)$ denote the set of all subsets of V which separate s from l. By using every Gomory Hu tree of $\mathcal {S}$ we can obtain an element of $\varGamma (s, l)$ which has minimum value among all the elements of $\varGamma (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 $\mathcal {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 $\mathcal {S}$ with respect to some subsets of V only by using contraction in Gomory Hu tree of $\mathcal {S}.$ Furthermore, we obtain some pendant pairs of $\mathcal {S}$ and its contractions by using a Gomory Hu tree of $\mathcal {S}$.
Origin | Files produced by the author(s) |
---|
Loading...