Algoritmo di Kernighan-Lin

L'algoritmo Kernighan–Lin è un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessità computazionale ${\displaystyle O(n^{2}\log n)}$.

Algoritmo di Kernighan-Lin
Classe	Grafi
Struttura dati	grafico ponderato
Caso peggiore temporalmente	O(n^2 \log n)

Questo algoritmo, proposto nel 1970 da Shen Lin e Brian Kernighan, ha importanti applicazioni per la progettazione di circuiti digitali e VLSI.

Descrizione

Si consideri il grafo ${\displaystyle G=(V,E)}$, dove ${\displaystyle V}$ denota l'insieme dei vertici ed ${\displaystyle E}$ l'insieme degli archi.

L'algoritmo mira a trovare una partizione di ${\displaystyle V}$ in due sottoinsiemi ${\displaystyle A}$ e ${\displaystyle B}$ di uguale cardinalità, tali che la somma ${\displaystyle T}$ del costo degli archi fra elementi di ${\displaystyle A}$ e ${\displaystyle B}$ sia minimizzato.

In particolare, se si denota con

${\displaystyle I_{a}}$ il costo interno di ${\displaystyle a}$ (cioè la somma del costo degli archi fra ${\displaystyle a}$ e altri elementi che sono nello stesso sottoinsieme, sia esso ${\displaystyle A}$ o ${\displaystyle B}$)

${\displaystyle E_{a}}$ il costo esterno (cioè la somma del costo degli archi fra ${\displaystyle a}$ e tutti gli altri vertici che non appartengono al medesimo insieme di ${\displaystyle a}$)

${\displaystyle D_{a}=E_{a}-I_{a}}$ la differenza di costo

Allora si ha che se si scambiano due elementi ${\displaystyle a}$ e ${\displaystyle b}$ (uno appartenente ad ${\displaystyle A}$, l'altro a ${\displaystyle B}$), si ha una riduzione di costo

${\displaystyle T_{vecchio}-T_{nuovo}=D_{a}+D_{b}-2c_{a,b}}$

dove con ${\displaystyle c_{a,b}}$ si denota il costo dell'arco fra ${\displaystyle a}$ e ${\displaystyle b}$.

L'algoritmo cerca una sequenza ottimale di permutazioni di un elemento di ${\displaystyle A}$ e uno di ${\displaystyle B}$ tale da massimizzare${\displaystyle T_{vecchio}-T_{nuovo}}$.^[1] its one of the optimized algorithms.

Pseudocodice

Vedi^[2]

 1  function Kernighan-Lin(G(V,E)):
 2      determina una partizione iniziale dei vertici in A e B
 3      do
 4         A1 := A; B1 := B
 5         calcola D per tutti gli a in A1 e b in B1
 6         for (i := 1 to |V|/2)
 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] ] è massimale
 8            sposta a[i] a B1 e b[i] ad A1
 9            tralascia a[i] e b[i] da ulteriori considerazioni
 10           aggiorna i valori di D per gli elementi di A1 = A1 /{a[i]} and B1 = B1 /{b[i]}
 11        end for
 12        trova k che massimizza g_max=g[1] + ... +g[k]
 13        if (g_max > 0) then
 14           Scambia a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
 15     until (g_max <= 0)
 16  return G(V,E)