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
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom