On minimizing symmetric set functions (Q5928598): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s004930070017 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1557119628 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 20:10, 19 March 2024
scientific article; zbMATH DE number 1583181
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On minimizing symmetric set functions |
scientific article; zbMATH DE number 1583181 |
Statements
On minimizing symmetric set functions (English)
0 references
1 April 2001
0 references
\textit{W. Mader} [Arch. Math. 23, 553-560 (1972; Zbl 0228.05119)] showed that every loopless graph contains a pair of vertices \((u,v)\) such that the star of \(v\) is a minimium cut separating \(u\) and \(v\). Later it was shown that the last two nodes of a ``max-back order'' have this property and this has been used to develop a nice min-cut algorithm and to minimize symmetric submodular functions. It is shown in this paper that the same algorithm works for an even more general class of set functions.
0 references
minimum cut
0 references
submodular function
0 references
