A note on the separation problem for the matching matroid
For a graph G having vertex set V, the matching matroid of G is the matroid on V that has as its independent sets all subsets X of V such that G has a matching whose set of endpoints contains X. If r is the rank function of this matroid the associated polyhedron \({\mathcal P}\) is defined by \({\mathcal P}=\{x\in {\mathbb{R}}_+^ v: x(A)\leq r(A)\) for all \(A\subseteq V\}\). Thus \({\mathcal P}\) is the convex hull of the incidence vectors of the independent sets of the matching matroid. This paper considers the following separation problem: determine whether a given member x of \({\mathbb{R}}_+^ v\) belongs to \({\mathcal P}\) and, if it does not, find a subset A of V for which \(x(A)>r(A).\) The author solves this problem by reducing it to the problem of finding a minimum-capacity cut on a certain digraph.
- Separation par une droite dans les matroïdes orientés de rang 3. (Separation of oriented matroids of rang 3 by a line)
- The optimal path-matching problem
- A separation algorithm for the matchable set polytope
- Characterizing matchings as the intersection of matroids
- On some algorithmic aspects of hypergraphic matroids
- Facets of the independent path-matching polytope
- The disjunctive procedure on the matching problem
- scientific article; zbMATH DE number 4174676 (Why is no real title available?)
- On the geometric rank of matching polytope
- Bridging Separations in Matroids
- A note on matchings and separability
This page was built for publication: A note on the separation problem for the matching matroid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760436)
