{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q760436","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q760436","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q760436","kernelVersion":"v1","immutable":true,"modified":"2026-01-05T19:59:38Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q760436","name":"A note on the separation problem for the matching matroid","headline":"A note on the separation problem for the matching matroid","description":"scientific article; zbMATH DE number 3884183","url":"https://portal.mardi4nfdi.de/entity/Q760436","datePublished":"1984-00-00","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q760435"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q175483"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/0012-365X(84)90094-3","url":"https://doi.org/10.1016/0012-365X(84)90094-3"},"sameAs":["https://doi.org/10.1016/0012-365X(84)90094-3"],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3932816"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5341586"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5516086"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4111952"}]},"provenance":{"prov:generatedAtTime":"2026-01-05T19:59:38Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}