On minimizing symmetric set functions (Q5928598): Difference between revisions

\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.