1. On the polyhedral structure of uniform cut polytopes
- Author
-
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), and Centre National de la Recherche Scientifique (CNRS)
- Subjects
Convex hull ,Discrete mathematics ,medicine.medical_specialty ,Applied Mathematics ,Maximum cut ,Graph partitioning ,Polyhedral combinatorics ,Uniform cut polytopes ,Polytope ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Combinatorics ,Minimum cut ,medicine ,Mathematics::Metric Geometry ,Discrete Mathematics and Combinatorics ,Polytope model ,K-tree ,Mathematics ,Regular polytope - Abstract
International audience; A uniform cut polytope is defined as the convex hull of the incidence vectors of all cuts in an undirected graph G 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 k of one side of the cut is equal to 1 or 2. For larger values of k, 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
- Published
- 2014
- Full Text
- View/download PDF