Kernighan–Lin algorithm

The Kernighan -Lin algorithm is a heuristic algorithm by Brian W. Kernighan and Shen Lin to solve the graph partitioning problem. In practice, it is used to optimize the placement of components on one chip. The length of the conduits between the components should be kept to a minimum.

Description

Be an edge- weighted graph with vertex set and edge set. The algorithm is to divide the same into two disjoint subsets A and B size so that the sum of the edge weights between A and B will be minimal. The internal costs of A, ie the sum of all edge weights outgoing from node a in A, is referred to as. are the external costs of a node, ie the sum of all costs of the edges between a and the nodes in B.

Is the difference between the external and internal edge weights. If nodes a and b is replaced, is

Here, the cost of the edge between a and b.

The algorithm is now trying to replace the elements of the sets A and B optimally, so that is the maximum.