Canonical decompositions of symmetric submodular systems (Q760444)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Canonical decompositions of symmetric submodular systems |
scientific article |
Statements
Canonical decompositions of symmetric submodular systems (English)
0 references
1983
0 references
Consider a pair (E,f) in which E is a finite set and \(f: 2^ E\to R\) is a submodular function. Then, the submodular system (E,f) is called symmetric, if \(f(A)=f(E-A)\) for any \(A\subseteq E\). Any \(C\subseteq E\) such that \(| C| \geq 2\), \(| E-C| \geq 2\) is called a 2-cut of (E,f). By using the set of 2-cuts of (E,f) with a certain minimal value of f and a concept of aggregation associated with a partition of E, a canonical decomposition of the symmetric submodular systems has been defined. This decomposition can be represented by a tree showing the hierarchical structure of the reducible 2-cut aggregations. The theory is a generalization of the decomposition theory of 2-connected graphs developed by Tutte. Other examples of symmetric submodular systems associated to classes of graphs and matroids, for which this decomposition theory can be applied are also given.
0 references
irreducible partition
0 references
aggregation
0 references
decomposition
0 references
symmetric submodular systems
0 references
2-cut
0 references