Facets of the independent path-matching polytope |
| |
Authors: | K.K.H. Cheung |
| |
Affiliation: | School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6, Canada |
| |
Abstract: | Cunningham and Geelen introduced the independent path-matching problem as a common generalization of the weighted matching problem and the weighted matroid intersection problem. Associated with an independent path-matching is an independent path-matching vector. The independent path-matching polytope of an instance of the independent path-matching problem is the convex hull of all the independent path-matching vectors. Cunningham and Geelen described a system of linear inequalities defining the independent path-matching polytope. In this paper, we characterize which inequalities in this system induce facets of the independent path-matching polytope, generalizing previous results on the matching polytope and the common independent set polytope. |
| |
Keywords: | Facets Polytope Matching Matroid Path-matching |
本文献已被 ScienceDirect 等数据库收录! |
|