Size-constrained graph partitioning polytopes

DOI10.1016/j.disc.2010.08.009zbMath1219.05142OpenAlexW2018573643MaRDI QIDQ607006

F. Aykut Özsoy, Martine Labbé

Publication date: 19 November 2010

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

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

zbMATH Keywords

graph partitioningpolyhedral analysissize constraints

Mathematics Subject Classification ID

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

Related Items

An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment, An overview of graph covering and partitioning, Iterated maxima search for the maximally diverse grouping problem, An extended edge-representative formulation for the \(K\)-partitioning problem, Stochastic graph partitioning: quadratic versus SOCP formulations, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, An exact approach for the multi-constraint graph partitioning problem, The sport teams grouping problem, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, Improved compact formulations for a wide class of graph partitioning problems in sparse graphs, Balanced Partition of a Graph for Football Team Realignment in Ecuador, Political districting to minimize cut edges

Cites Work

• A branch-and-cut algorithm for the partitioning-hub location-routing problem
• Facets of the clique partitioning polytope
• A cutting plane algorithm for a clustering problem
• The node capacitated graph partitioning problem: A computational study
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• Min-cut clustering
• Graph partitioning using linear and semidefinite programming
• \(b\)-tree facets for the simple graph partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Clustering categorical data sets using tabu search techniques
• The partition problem
• Facet-defining inequalities for the simple graph partitioning polytope
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• A mixed-integer programming approach to the clustering problem with an application in customer segmentation
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Clique-Web Facets for Multicut Polytopes
• Realignment in the National Football League: Did they do it right?
• The clique partitioning problem: Facets and patching facets