Conference Papers Year : 2017

Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System

Saeid Hanifehnezhad
  • Function : Author
  • PersonId : 1030365
Ardeshir Dolati
  • Function : Author
  • PersonId : 1030363

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.

Fichier principal
Vignette du fichier
440117_1_En_3_Chapter.pdf (264) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01760643 , version 1 (06-04-2018)

Licence

Identifiers

Cite

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⟩
268 View
152 Download

Altmetric

Share

  • More