Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

b-tree facets for the simple graph partitioning polytope

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • 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.
Udgivelsesdato: JUN
TidsskriftJournal of Combinatorial Optimization
Sider (fra-til)151-170
Antal sider20
StatusUdgivet - 2004


  • Clustering, Graph partitioning, Multicuts, Polyhedral combinatorics

Se relationer på Aarhus Universitet Citationsformater

ID: 32324350