Co więcej, gdy wszystkie zyski z zamian w danej iteracji będą ujemne (zamiana zwiększy sumę krawędzi łączących podgrafy), to algorytm działa dalej, gdyż być może kolejne zamiany okażą się lepsze.
Pseudokod 1 function Kernighan-Lin(G(V,E)): 2 determine a balanced initial partition of the nodes into sets A and B 3 do 2 A1 := A; B1 := B 4 compute D values for all a in A1 and b in B1 5 for (i := 1 to |V|/2) 6 find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal 7 move a[i] to B1 and b[i] to A1 8 remove a[i] and b[i] from further consideration in this pass 9 update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i] 10 end for 11 find k which maximizes g_max, the sum of g,...,g[k] 12 if (g_max > 0) then 13 Exchange a,a,...,a[k] with b,b,...,b[k] 14 until (g_max <= 0) 15 return G(V,E)
Zobacz też Brian Kernighan
Bibliografia Kernighan, B.W.; Lin, Shen (1970). An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49: 291–307. Ravikumār, Si. Pi; Ravikumar, C.P (1995). Parallel methods for VLSI layout design. Greenwood Publishing Group. s. 73. . OCLC 2009-06-12.
Kategoria:Algorytmy grafowe