# Kernighan–Lin algorithm

(Redirected from Kernighan–Lin)
Jump to: navigation, search
This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesperson problem, see Lin–Kernighan heuristic.

Kernighan–Lin is a O(n2 log(n)) heuristic algorithm for solving the graph partitioning problem. The algorithm has important applications in the layout of digital circuits and components in VLSI.[1][2]

## Description

Let ${\displaystyle G(V,E)}$ be a graph, and let ${\displaystyle V}$ be the set of nodes and ${\displaystyle E}$ the set of edges. The algorithm attempts to find a partition of ${\displaystyle V}$ into two disjoint subsets ${\displaystyle A}$ and ${\displaystyle B}$ of equal size, such that the sum ${\displaystyle T}$ of the weights of the edges between nodes in ${\displaystyle A}$ and ${\displaystyle B}$ is minimized. Let ${\displaystyle I_{a}}$ be the internal cost of a, that is, the sum of the costs of edges between a and other nodes in A, and let ${\displaystyle E_{a}}$ be the external cost of a, that is, the sum of the costs of edges between a and nodes in B. Furthermore, let

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

be the difference between the external and internal costs of a. If a and b are interchanged, then the reduction in cost is

${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}$

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

The algorithm attempts to find an optimal series of interchange operations between elements of ${\displaystyle A}$ and ${\displaystyle B}$ which maximizes ${\displaystyle T_{old}-T_{new}}$ and then executes the operations, producing a partition of the graph to A and B.[1]

## Pseudocode

See [2]

`````` 1  function Kernighan-Lin(G(V,E)):
2      determine a balanced initial partition of the nodes into sets A and B
3
4      do
5         compute D values for all a in A and b in B
6         let gv, av, and bv be empty lists
7         for (n := 1 to |V|/2)
8            find a from A and b from B, such that g = D[a] + D[b] - 2*E(a, b) is maximal
9            remove a and b from further consideration in this pass
10           add g to gv, a to av, and b to bv
11           update D values for the elements of A = A \ a and B = B \ b
12        end for
13        find k which maximizes g_max, the sum of gv[1],...,gv[k]
14        if (g_max > 0) then
15           Exchange av[1],av[2],...,av[k] with bv[1],bv[2],...,bv[k]
16     until (g_max <= 0)
17  return G(V,E)
```
```

## References

1. ^ a b Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal. 49: 291–307. doi:10.1002/j.1538-7305.1970.tb01770.x.
2. ^ a b Ravikumār, Si. Pi; Ravikumar, C.P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. p. 73. ISBN 978-0-89391-828-6.