b"\n_START_ARTICLE_\nAlgoritmo di Kernighan-Lin\n_START_PARAGRAPH_\nL'algoritmo Kernighan\xe2\x80\x93Lin \xc3\xa8 un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessit\xc3\xa0 computazionale O(n^2 \\log n)._NEWLINE_Questo algoritmo, proposto nel 1970 da Shen Lin e Brian Kernighan, ha importanti applicazioni per la progettazione di circuiti digitali e VLSI.\n_START_SECTION_\nPseudocodice\n_START_PARAGRAPH_\nVedi_NEWLINE__NEWLINE_ 1  function Kernighan-Lin(G(V,E)):_NEWLINE_ 2      determina una partizione iniziale dei vertici in A e B_NEWLINE_ 3      do_NEWLINE_ 4         A1 := A; B1 := B_NEWLINE_ 5         calcola D per tutti gli a in A1 e b in B1_NEWLINE_ 6         for (i := 1 to |V|/2)_NEWLINE_ 7            trova a[i] da A1 e b[i] da B1 tali che g[i] = D[a[i] ] + D[b[i] ] - 2*c[a[i] ][b[i] ] \xc3\xa8 massimale_NEWLINE_ 8            sposta a[i] a B1 e b[i] ad A1_NEWLINE_ 9            tralascia a[i] e b[i] da ulteriori considerazioni_NEWLINE_ 10           aggiorna i valori di D per gli elementi di A1 = A1 /{a[i]} and B1 = B1 /{b[i]}_NEWLINE_ 11        end for_NEWLINE_ 12        trova k che massimizza g_max=g[1] + ... +g[k]_NEWLINE_ 13        if (g_max > 0) then_NEWLINE_ 14           Scambia a[1],a[2],...,a[k] with b[1],b[2],...,b[k]_NEWLINE_ 15     until (g_max <= 0)_NEWLINE_ 16  return G(V,E)"