Search

Your search keyword '"Uniform cut polytopes"' showing total 4 results
Start Over Descriptor "Uniform cut polytopes" Database OpenAIRE
4 results on '"Uniform cut polytopes"'

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

2. From equipartition to uniform cut polytopes: Extended polyhedral results

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, 021103 operations research, Polyhedral combinatorics, Graph partitioning, 0211 other engineering and technologies, Graph partition, Uniform k 21 polytope, Polytope, Uniform cut polytopes, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Polyhedron, 010201 computation theory & mathematics, Cut, Convex polytope, medicine, Mathematics::Metric Geometry, Discrete Mathematics and Combinatorics, Mathematics
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.

Published
2011
Full Text
View/download PDF

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

4. From equipartition to uniform cut polytopes : polyhedral results extended

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
Graph partitioning, Mathematics::Metric Geometry, Uniform cut polytopes, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

Given an undirected graph, a uniform cut polytope is defined as the convex hull of the incidence vectors of cuts 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. provide facet defining inequalities for uniform cut polyhedra

Published
2009

Catalog

Books, media, physical & digital resources
See catalog results