Algoritmo di Kernighan-Lin

L'algoritmo Kernighan–Lin è un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessità computazionale $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 $G=(V,E)$, dove $V$ denota l'insieme dei vertici ed $E$ l'insieme degli archi.

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

In particolare, se si denota con

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

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

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

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

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

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

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

Pseudocodice

Vedi

 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)