Aarhus University Seal / Aarhus Universitets segl

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

Research output: Working paperResearch

  • Department of Business Studies
  • 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.
Original languageEnglish
Publication statusPublished - 1999

    Research areas

  • Heuristics, Clusering, Group technology, HHÅ forskning

See relations at Aarhus University Citationformats

ID: 32297550