Title of article :
On the cut polyhedron
Author/Authors :
Michele Conforti، نويسنده , , Giovanni Rinaldi، نويسنده , , Laurence Wolsey، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Abstract :
For an undirected connected graph G, the cut polyhedron cut(G) is the dominant of the convex hull of the incidence vectors of all nonempty edge cutsets of G. We give some properties of the facial structure of cut(G). In particular, we characterize all of the facet-inducing inequalities with right-hand side at most 2. These include all of the rank facets of cut(G).
Keywords :
Minimum cut , Cut polyhedron , Facet-inducing inequality , Rank inequality
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics