Excluded minors for Boolean polymatroids (Q5937943): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 00:43, 5 March 2024
scientific article; zbMATH DE number 1621252
Language | Label | Description | Also known as |
---|---|---|---|
English | Excluded minors for Boolean polymatroids |
scientific article; zbMATH DE number 1621252 |
Statements
Excluded minors for Boolean polymatroids (English)
0 references
23 October 2001
0 references
A polymatroid function \(h: 2^N\to \mathbb{Z}\) is Boolean if it can be represented in the form \(h(I)=|\bigcup_{i\in I}\phi(i)|\) for a set function \(\phi: N\to 2^M\). Necessary and sufficient conditions for a polymatroid to be Boolean are presented by describing \(h\) as a linear combination over rank-one matroids or equivalently requiring a linear operator on \(h\) to be positive, which yields \(2^n -1\) inequalities. The main result is an explicit description of all excluded minors of the class of Boolean polymatroids.
0 references
Boolean polymatroid
0 references
excluded minors
0 references