From equipartition to uniform cut polytopes: extended polyhedral results

DOI10.1016/j.disc.2011.01.018zbMath1222.05215OpenAlexW2069946405MaRDI QIDQ533779

José Neto

Publication date: 6 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.01.018

zbMATH Keywords

graph partitioninguniform cut polytopes

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On the diameter of cut polytopes, On the polyhedral structure of uniform cut polytopes

Cites Work

• Unnamed Item
• The node capacitated graph partitioning problem: A computational study
• A branch-and-cut algorithm for the equicut problem
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Some new classes of facets for the equicut polytope
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Via Minimization with Pin Preassignments and Layer Preference
• On the Graph Bisection Cut Polytope
• Facets of the Bipartite Subgraph Polytope
• On the cut polytope
• Geometry of cuts and metrics