Skip to Main content Skip to Navigation
Conference papers

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}$.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01760643
Contributor : Hal Ifip <>
Submitted on : Friday, April 6, 2018 - 3:08:08 PM
Last modification on : Friday, April 6, 2018 - 3:19:08 PM

File

440117_1_En_3_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Saeid Hanifehnezhad, Ardeshir Dolati. Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System. 2nd International Conference on Topics in Theoretical Computer Science (TTCS), Sep 2017, Tehran, Iran. pp.26-33, ⟨10.1007/978-3-319-68953-1_3⟩. ⟨hal-01760643⟩

Share

Metrics

Record views

321

Files downloads

95