Symmetric submodular system: Contractions and Gomory-Hu tree

Ardeshir Dolatimalekabad | Saeid Hanifehnezhad

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=147960
Date :  2020/04/01
Publish in :    Information and Computation
DOI :  https://doi.org/https://doi.org/10.1016/j.ic.2019.104479
Link :  https://www.sciencedirect.com/science/article/abs/pii/S0890540119300951?via3Dihubaep-article-footnote-id1
Keywords :Symmetric submodular system, Contraction of a system, Pendant pair, Maximum adjacency ordering, Gomory-Hu tree, Minimum cut

Abstract :

---

Let S=(V,f), be a symmetric submodular system. For two distinct elements s and l of V, let denote the set of all subsets of V which separate s from l. By using any Gomory-Hu tree of S we can obtain an element of which has minimum value among all the elements of . This tree can be constructed iteratively by solving V-1 minimum sl_separator problem. 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 a Gomory-Hu tree of S. Furthermore, we obtain some pendant pairs of and of its contractions by using a Gomory-Hu tree of S