Kernighan–Lin algorithm

From Wikipedia, the free encyclopedia
  (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[edit]

Let be a graph, and let be the set of nodes and the set of edges. The algorithm attempts to find a partition of into two disjoint subsets and of equal size, such that the sum of the weights of the edges between nodes in and is minimized. Let be the internal cost of a, that is, the sum of the costs of edges between a and other nodes in A, and let be the external cost of a, that is, the sum of the costs of edges between a and nodes in B. Furthermore, let

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

where 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 and which maximizes and then executes the operations, producing a partition of the graph to A and B.[1]

Pseudocode[edit]

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[edit]

  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.