Integral polyhedra related to even-cycle and even-cut matroids

• 成果类型: Article
• 署名作者: Guenin, B
• 署名单位: University of Waterloo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.27.4.693.299
• 发表日期: 2002
• 页码: 693-710
• 关键词: PROPERTY

摘要

A family of sets H is ideal if the polyhedron {x greater than or equal to 0:Sigma(iis an element ofS) x(i).greater than or equal to 1, For All S is an element of H} is integral. Consider a graph G with vertices s, t. An odd st-walk is either an odd st-path or the union of an even st-path and an odd circuit that share, at most, one vertex. Let T be a subset of vertices of even cardinality. An st-T-cut is a cut of the form delta(U) where \U boolean AND T\ is odd and U contains exactly one of s or t. We give excluded minor characterizations for when the families of odd st-walks and st-T-cuts (represented as sets of edges) are ideal. As a corollary, we characterize which extensions and coextensions of graphic and cographic matroids are 1-flowing.