Technical Report 393-1994

Title

A Combinatorial Algorithm for Minimizing Symmetric Submodular Functions

Author

Maurice Queyranne

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

We describe a purely combinatorial algorithm which, given a submodular set function f on a finite set V, finds a proper subset A of V minimizing f[A]+f[Vsetminus A]. This algorithm, an extension of the Nagamochi-Ibaraki minimum cut algorithm as simplified by Stoer and Wagner (1994) and by Frank (1994), minimizes any symmetric submodular function using O(|V|³) calls to a function value oracle.