Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

b-Tree Facets for the Simple Graph Partitioning Polytope

Publikation: Working paperForskning

  • Erhvervsøkonomisk Institut
  • 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.
OriginalsprogEngelsk
StatusUdgivet - 2000

    Forskningsområder

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

Se relationer på Aarhus Universitet Citationsformater

ID: 32298279