 #jsDisabledContent { display:none; } My Account |  Register |  Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

# Kernighan–Lin algorithm

Article Id: WHEBN0023174224
Reproduction Date:

 Title: Kernighan–Lin algorithm Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Kernighan–Lin algorithm

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.

## Description

Let G(V,E) be a graph, and let V be the set of nodes and E the set of edges. The algorithm attempts to find a partition of V into two disjoint subsets A and B of equal size, such that the sum T of the weights of the edges between nodes in A and B is minimized. Let 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 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

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

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

where 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 A and B which maximizes T_{old} - T_{new} and then executes the operations, producing a partition of the graph to A and B.

## Pseudocode

See 

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