On minimizing symmetric set functions

DOI10.1007/S004930070017MaRDI QIDQ5928598zbMATH OpenOpenAlexFDO

Authors Romeo Rizzi

Publication date 1 April 2001

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930070017

zbMATH Keywords

minimum cutsubmodular function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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

Recommendations

• Minimizing symmetric submodular functions
• Minimum degree orderings
• scientific article; zbMATH DE number 910864
• Minimum Degree Orderings
• A note on minimizing submodular functions

Cited in

(10)

• Realization of set functions as cut functions of graphs and hypergraphs
• Realizing symmetric set functions as hypergraph cut capacity
• scientific article; zbMATH DE number 4144267 (Why is no real title available?)
• Minimum cuts, modular functions, and matroid polyhedra
• Minimum cuts and sparsification in hypergraphs
• The minimal Denjoy index of a symmetric perfect set
• Excluding a simple good pair approach to directed cuts
• Graph connectivity and its augmentation: Applications of MA orderings
• Minimum degree orderings
• Submodular function minimization

This page was built for publication: On minimizing symmetric set functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928598)