Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

Facet Defining Inequalities for the Simple Graph Partioning 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 containing at most b nodes, such that the sum of the weights of all edges in the subgraphs is maximal. In this paper we investigate the facial structure of the simple graph partitioning polytopes P(b), b = 3,...,n, associated with the complete graph on n nodes. In particular we introduce two new classes af facet defining inequalities that are induced by cliques and multistars.
StatusUdgivet - 2000


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

Se relationer på Aarhus Universitet Citationsformater

ID: 2103