Aarhus University Seal / Aarhus Universitets segl

Michael Malmros Sørensen

An Adaptation of the Kernighan-Lin Heuristic to the Simple Graph Partitioning Problem

Publikation: Working paperForskning

  • Erhvervsøkonomisk Institut
  • CORAL - Centre for Operations Research Applications in Logistics
The simple graph partitioning problem is to partition a simple, 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 describe and evaluate an adaptation to this problem of the Kernighan-Lin exchange heuristic, which was originally developed for the closely related 2-partition problem. The evaluation is carried out on problem instances on graphs with up to 50 nodes for which the optimal partition values are known or upper bounds are available. The computational results show that among all instances with known optimal values the best partition values found by a randomized version of this heuristic lie well within 1% off the optimum.
StatusUdgivet - 1999


  • Heuristics, Clusering, Group technology, HHÅ forskning

Se relationer på Aarhus Universitet Citationsformater

ID: 32297550