Aarhus University Seal

b-Tree Facets for the Simple Graph Partitioning Polytope

Research output: Working paper/Preprint Working paperResearch

  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
The simple graph partitioning problem is to partition an edge-weighted graph into mutually disjoint subgraphs, each consisting of no more than b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we introduce a large class of facet defining inequalities for the simple graph partitioning polytopes P_n(b), b >= 3, associated with the complete graph on n nodes. These inequalities are induced by a graph configuration which is built upon trees of cardinality b. We provide a closed-form theorem that states all necessary and sufficient conditions for the facet defining property of the inequalities.
Translated title of the contributionb-Tree Facets for the Simple Graph Partitioning Polytope
Original languageEnglish
Publication statusPublished - 2000

    Research areas

  • Clustering, Graph partitioning, Multicuts, Facets, Polyhedra, HHÅ forskning

See relations at Aarhus University Citationformats

ID: 32298279