首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Facets of the independent path-matching polytope
Authors:KKH Cheung
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号