Aarhus University Seal / Aarhus Universitets segl

b-tree facets for the simple graph partitioning polytope

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • 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.
Udgivelsesdato: JUN
Original languageEnglish
JournalJournal of Combinatorial Optimization
Volume8
Issue2
Pages (from-to)151-170
Number of pages20
ISSN1382-6905
Publication statusPublished - 2004

    Research areas

  • Clustering, Graph partitioning, Multicuts, Polyhedral combinatorics

See relations at Aarhus University Citationformats

ID: 32324350