Connectivity of submodular functions (Q1199483)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connectivity of submodular functions |
scientific article |
Statements
Connectivity of submodular functions (English)
0 references
16 January 1993
0 references
This paper relates the connectivity of submodular functions \(f\) to that of certain submodular functions which are derived from \(f\). Here the function \(f\) on \(S\) is submodular if \(f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\) for all subsets \(A\) and \(B\) of \(S\). The connectivity function \(c_ f\) of the submodular function \(f\) on \(S\) is defined by \(c_ f(A)=f(A)+f(S-A)- f(S)-f(0)\) for all subsets \(A\) of \(S\). The authors defined \(\overline c_ f\) to be minimum value that \(c_ f\) takes on nonempty proper subsets of \(S\) unless \(| S|\leq 1\). One of the two main results of this paper generalizes Tutte's result to submodular functions. This shows that if for a subset \(A\) of the ground set \(S\) we have \(c_ f(A)<2\overline c_ f\) then at least one of the operations of delection of \(A\) from \(f\) and of contraction of \(A\) from \(f\) is connected. In the second section of this paper is introduced and investigated a new operation on submodular functions which does correspond to contraction in graphs.
0 references
connectivity function
0 references
submodular function
0 references