Premium
Minimum cuts, modular functions, and matroid polyhedra
Author(s) -
Cunningham William H.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150206
Subject(s) - matroid , submodular set function , polyhedron , mathematics , modular design , combinatorics , equivalence (formal languages) , function (biology) , minification , discrete mathematics , mathematical optimization , computer science , evolutionary biology , biology , operating system
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.