Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/72219
Type: Artigo de periódico
Title: The perfect matching polytope and solid bricks
Author: de Carvalho, MH
Lucchesi, CL
Murty, USR
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 Q(E) belongs to the perfect matching polytope of G if and only if it satisfies the inequalities: (i) x greater than or equal to 0 (non-negativity), (ii) x (partial derivative(v)) = 1, for all v is an element of V (degree constraints) and (iii) x(partial derivative(S)) greater than or equal to 1, 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. (C) 2004 Elsevier Inc. All rights reserved.
Subject: matchings
the perfect matching polytope
bricks
Country: EUA
Editor: Academic Press Inc Elsevier Science
Rights: fechado
Identifier DOI: 10.1016/j.jctb.2004.08.003
Date Issue: 2004
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000225169100007.pdf166.19 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.