Mader proved that every loopless undirected graph
contains a pair (
u,
v) of nodes such that
the star of
v is a minimum
cut separating
u and
v.
Nagamochi and Ibaraki
showed that the last two nodes of a ``legal
ordering'' form such a pair and used this fact
to develop an elegant min-cut algorithm.
M. Queyranne extended this approach to minimize
symmetric submodular functions.
With the help of a short and simple proof,
we now show that the same algorithm works
for an even more general class of set functions.
Key words: legal ordering,
minimum cut,
symmetric submodular functions,
greedy order.
