From equipartition to uniform cut polytopes: Extended polyhedral results

Authors :: José Neto
Département Réseaux et Services Multimédia Mobiles (RS2M)
Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)
Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR)
Centre National de la Recherche Scientifique (CNRS)
Source :: Discrete Mathematics, Discrete Mathematics, Elsevier, 2011, 311 (8 & 9), pp.705-714. ⟨10.1016/j.disc.2011.01.018⟩
Publication Year :: 2011
Publisher :: Elsevier BV, 2011.
Abstract: International audience; Given an undirected graph G, a uniform cut polytope is defined as the convex hull of the incidence vectors of the cuts in G for which the size of the shores are fixed. In this paper we show that simple extensions of facet-defining inequalities for the equipartition polytope introduced by Conforti et al. in [5] and [6] provide facet-defining inequalities for uniform cut polyhedra.