Optimum matching forests III: Facets of matching forest polyhedra |
| |
Authors: | Rick Giles |
| |
Affiliation: | (1) Department of Mathematics, University of Kentucky, 40506 Lexington, KY, USA |
| |
Abstract: | In [3] we presented a linear system which definesP(G), the convex hull of incidence vectors of matching forests of a mixed graphG. However, many of the inequalities of this system may be redundant. Here we describe the dimension of the facets ofP(G) obtained by setting one inequality of the defining system forP(G) to an equation. This leads to a presentation of a minimal defining linear system forP(G), i.e., to a presentation of the facets ofP(G). This generalizes earlier characterizations of facets of 1-matching polyhedra and of branching polyhedra.Research partially supported by a N.R.C. Canada Postdoctorate Fellowship. |
| |
Keywords: | Graph Matching Branching Polyhedron Facet |
本文献已被 SpringerLink 等数据库收录! |
|