Balanced sets in an independence structure induced by a submodular function |
| |
Authors: | Jeremy E Dawson |
| |
Affiliation: | CSIRO Division of Mathematics and Statistics, Sydney, Australia |
| |
Abstract: | A submodular (and non-decreasing) function on a set induces an independence structure; the notion of a “balanced” set in this situation helps us determine whether a given independence structure is induced by any submodular function other than its own rank function, answering a question of U. S. R. Murty and I. Simon. The notion “balanced” also has a natural meaning when one independence structure is induced from another across a bipartite graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|