Facet-defining inequalities for the simple graph partitioning polytope

DOI10.1016/J.DISOPT.2006.08.001MaRDI QIDQ2467133zbMATH OpenOpenAlexFDO

Authors Michael Malmros Sørensen

Publication date 18 January 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.08.001

zbMATH Keywords

clusteringfacetgraph partitioningmulticutpolyhedral combinatorics

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• \(b\)-tree facets for the simple graph partitioning polytope
• The partition problem
• Separation of partition inequalities
• Facets of the clique partitioning polytope
• The clique partitioning problem: Facets and patching facets

Cites work

• \(b\)-tree facets for the simple graph partitioning polytope
• A branch-and-cut algorithm for the equicut problem
• A cutting plane algorithm for a clustering problem
• A Note on Clique-Web Facets for Multicut Polytopes
• Clique-Web Facets for Multicut Polytopes
• Efficient Algorithm for the Partitioning of Trees
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Facets of the \(k\)-partition polytope
• Facets of the clique partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 3991298 (Why is no real title available?)
• scientific article; zbMATH DE number 15357 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• On Linear Characterizations of Combinatorial Optimization Problems
• On the cut polytope
• Some new classes of facets for the equicut polytope
• The clique partitioning problem: Facets and patching facets
• The discrete p-dispersion problem
• 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

Cited in

(16)

• 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
• \(b\)-tree facets for the simple graph partitioning polytope
• Polyhedral properties of the induced cluster subgraphs
• Political districting to minimize cut edges
• An overview of graph covering and partitioning
• The partition problem
• Partition inequalities: separation, extensions, and network design
• 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 Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• The clique partitioning problem: Facets and patching facets
• Size-constrained graph partitioning polytopes
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations

This page was built for publication: Facet-defining inequalities for the simple graph partitioning polytope

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