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


The perfect matching polytope and solid bricks
Authors:Marcelo H de Carvalho  Cludio L Lucchesi  USR Murty
Institution:a UFMS, Campo Grande, Brasil;b University of Waterloo, Waterloo, Canada;c UNICAMP, Campinas, Brasil
Abstract:The perfect matching polytope of a graph G is the convex hull of the set of incidence vectors of perfect matchings of G. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69B 1965 125) showed that a vector x in QE belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) xgreater-or-equal, slanted0 (non-negativity), (ii) x(∂(v))=1, for all vset membership, variantV (degree constraints) and (iii) x(∂(S))greater-or-equal, slanted1, for all odd subsets S of V (odd set constraints). In this paper, we characterize graphs whose perfect matching polytopes are determined by non-negativity and the degree constraints. We also present a proof of a recent theorem of Reed and Wakabayashi.
Keywords:Matchings  The perfect matching polytope  Bricks
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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