Size-constrained graph partitioning polytopes

DOI10.1016/J.DISC.2010.08.009MaRDI QIDQ607006zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The partition problem
• On the solution of a graph partitioning problem under capacity constraints
• Facet-defining inequalities for the simple graph partitioning polytope
• Graph clustering with a constraint on cluster sizes
• The equipartition polytope. I: Formulations, dimension and basic facets

Cites work

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

Cited in

(16)

• An overview of graph covering and partitioning
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• The sport teams grouping problem
• An exact approach for the balanced \(k\)-way partitioning problem with weight constraints and its application to sports team realignment
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Clustering with lower-bounded sizes. A general graph-theoretic framework
• Integer programming models for detecting graph bipartitions with structural requirements
• Balanced partition of a graph for football team realignment in Ecuador
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• 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
• An exact approach for the multi-constraint graph partitioning problem
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs
• Political districting to minimize cut edges

This page was built for publication: Size-constrained graph partitioning polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607006)