Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421142 | Discrete Applied Mathematics | 2014 | 9 Pages |
Abstract
A uniform cut polytope is defined as the convex hull of the incidence vectors of all cuts in an undirected graph GG for which the cardinalities of the shores are fixed.In this paper, we study linear descriptions of such polytopes. Complete formulations are presented for the cases when the cardinality kk of one side of the cut is equal to 1 or 2. For larger values of kk, investigations with relation to the shape of these polytopes are reported. We namely determine their diameter and also provide new families of facet-defining inequalities.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
José Neto,