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

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

0.00 Avg rating0 Votes
Article ID: iaor2004856
Country: United States
Volume: 27
Issue: 4
Start Page Number: 693
End Page Number: 710
Publication Date: Nov 2002
Journal: Mathematics of Operations Research
Authors:
Keywords: programming: integer
Abstract:

A family of sets ℋ is ideal if the polyhedron {x ≥ 0 : Σi∈S xi ≥ 1, ∀ S ∈ ℋ} is internal. 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 δ(U) where |U ∩ T| is odd and U contains exactly one of s or t. We give excluded minor characterization 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.

Reviews

Required fields are marked *. Your email address will not be published.