Total dual integrality of matching forest constraints (Q5932756)
From MaRDI portal
scientific article; zbMATH DE number 1604314
Language | Label | Description | Also known as |
---|---|---|---|
English | Total dual integrality of matching forest constraints |
scientific article; zbMATH DE number 1604314 |
Statements
Total dual integrality of matching forest constraints (English)
0 references
13 June 2001
0 references
A matching forest in a mixed graph (that is, where some of the edges are oriented) has no circuit in the underlying undirected graph and each vertex has indegree at most one (counting heads of the directed edges and either end of the undirected edges). ``Giles gave a polynomial time algorithm to find a maximum weight matching forest, yielding as a by-product a characterization of the inequalities determining the convex hull of the incidence vectors of the matching forests.'' The author proves that these inequalities form a totally dual integral system.
0 references
matching forest
0 references
totally dual integral system
0 references