User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

On the cut polyhedron

Primary tabs

Wolsey, Laurence [UCL] Conforti, Michèle Rinaldi, Giovanni

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).

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2008
Journal information "Discrete Mathematics" - Vol. 277, no. 1-3, p. 279-285 (2008)
Peer reviewed yes
Publisher Elsevier (Amsterdam)
issn 0012-365X
Publication status Publié
Affiliation Louvain School of Management - Operations and Information
Keywords Rank inequality
Links
Bibliographic reference Wolsey, Laurence ; Conforti, Michèle ; Rinaldi, Giovanni. On the cut polyhedron. In: Discrete Mathematics, Vol. 277, no. 1-3, p. 279-285 (2008)
Permanent URL http://hdl.handle.net/2078/18081