1. On the diameter of cut polytopes
- Author
-
Neto, José, Méthodes et modèles pour les réseaux (METHODES-SAMOVAR), Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (SAMOVAR), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP)-Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Département Réseaux et Services Multimédia Mobiles (RS2M), Institut Mines-Télécom [Paris] (IMT)-Télécom SudParis (TSP), Centre National de la Recherche Scientifique (CNRS), Dépt. Réseaux et Service Multimédia Mobiles (Institut Mines-Télécom-Télécom SudParis), and Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux (Institut Mines-Télécom-Télécom SudParis-CNRS)
- Subjects
Diameter ,Graph partitioning ,Mathematics::Metric Geometry ,Uniform cut polytopes ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] - Abstract
Given an undirected graph G with node set V, the cut polytope is defined as the convex hull of the incidence vectors of all the cuts in G. And for a given integer k in the set {1,2,...,|V|-1}, the uniform cut polytope with parameter value k is defined as the convex hull of the cuts which correspond to a bipartition of the node set into sets with cardinalities k and |V|-k. In this paper, we study the diameter of these two families of polytopes. With respect to the cut polytope, we show a linear upper bound on its diameter (improving on one stemming from the reference: [F. Barahona and A.R. Mahjoub, On the cut polytope, Mathematical Programming 36, 157-173 (1986)]), give its value for trees and complete bipartite graphs. Then concerning uniform cut polytopes, we establish bounds on their diameter for different graph families, we provide some connections with other partition polytopes in the literature, and introduce sufficient and necessary conditions for adjacency on their 1-skeleton
- Published
- 2013