Algoritmo di Kernighan-Lin

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

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)}$.

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)

Note

1. B. W. Kernighan e Shen Lin, An efficient heuristic procedure for partitioning graphs, in Bell Systems Technical Journal, vol. 49, 1970, pp. 291–307.
2. Si. Pi Ravikumār, Ravikumar, C.P, Parallel methods for VLSI layout design, Greenwood Publishing Group, 1995, p. 73, ISBN 978-0-89391-828-6, OCLC 2009-06-12.