Kernighan-Lin algorithm

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

description

Let be an edge-weighted graph with node set and edge set . The algorithm should split into two disjoint subsets A and B of equal size, so that the sum of the edge weights between A and B is minimal. The internal costs of A, i.e. the sum of all edge weights starting from node a in A, is referred to as . be the external costs of node a, i.e. the sum of all costs of the edges between a and the nodes in B. ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle T}$ ${\displaystyle I_{a}}$ ${\displaystyle E_{a}}$

${\displaystyle D_{a}=E_{a}-I_{a}}$

is the difference between the external and internal edge weights. If nodes a and b are swapped, then

${\displaystyle T_{\text{alt}}-T_{\text{neu}}=D_{a}+D_{b}-2c_{a,b}}$,

here the cost of the edge is between a and b. ${\displaystyle c_{a,b}}$

The algorithm tries to swap the elements of the sets A and B optimally, so that becomes maximal. ${\displaystyle T_{\text{alt}}-T_{\text{neu}}}$

Individual evidence

1. ^ BW Kernighan, Shen Lin: An efficient heuristic procedure for partitioning graphs . In: Bell Systems Technical Journal . 49, 1970, pp. 291-307.