On the cut polyhedron

Michele Conforti, Giovanni Rinaldi and Laurence Wolsey

No 2000005, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The cut polyhedron cut(G) of an undirected graph G = (V, E) is the dominant of the convex hull of all of its nonempty edge cutsets. After examining various compact extended formulations for cut(G), we study some of its polyhedral properties. In particular, we characterize all of the facets induced by inequalities with right-hand side at most 2. These include all of the rank facets of the polyhedron.

Date: 2000-02-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2000.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2000005

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().