Minimum cuts, modular functions, and matroid polyhedra
William H. Cunningham · Networks · 1985
Abstract The minimum cut problem is a well‐solved special case of submodular function minimization. We show that it is in fact equivalent to minimizing a modular function over a ring family. One‐half of this equivalence follows from classical work of Rhys and Picard. We give a number of applications to testing membership in special kinds of matroid polyhedra.