Recognizing max-flow min-cut path matrices (Q1103514): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0167-6377(88)90050-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2007774717 / rank | |||
Normal rank |
Revision as of 23:58, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recognizing max-flow min-cut path matrices |
scientific article |
Statements
Recognizing max-flow min-cut path matrices (English)
0 references
1988
0 references
Let A be a 0,1-matrix, \(c\geq 0\) integral vector, and \(\mathbf{1}\) the vector of all 1's. Consider the following dual pair of linear programs: (P) minimize cx, subject to Ax\(\geq \mathbf{1}\), \(x\geq 0.\) (D) maximize \(y\mathbf{1}\), subject to yA\(\leq c\), \(y\geq 0.\) Seymour has shown that if A is a path matrix of a matroid M relative to an element e, then (P) and (D) have integral optimum solutions for every \(c\geq 0\) integral, iff M is binary and has no \(F\) \(*_ 7\) minor containing e. In this paper, a polynomial-time algorithm for determining whether a given 0,1-matrix is the path matrix of some binary matroid, is given. Combining this with an algorithm of Truemper to determine whether a matroid has an \(F\) \(*_ 7\) minor, leads to a polynomial-time algorithm for determining whether a given matrix A is in Seymour's class.
0 references
path matrix
0 references
polynomial-time algorithm
0 references
binary matroid
0 references